National Olympiad in Informatics, China, 1999

It is well-known that we can uniquely represent any point $P$ on the Cartesian coordinate system using an ordered pair $(x,y)$. If both $x$ and $y$ are integers, then we shall call $P$ an integer point, otherwise we shall call $P$ a non-integer point. We shall denote all integer points on the plane using the set $W$.

Definition 1: For two points $P_1(x_1,y_1),P_2(x_2,y_2)$, if $|x_1-x_2|+|y_1-y_2|=1$, then $P_1$ and $P_2$ shall be considered neighbors, which is denoted as $P_1\sim P_2$. Otherwise, $P_1$ and $P_2$ are considered non-neighboring.

Definition 2: The set $S$ is a finite subset of $W$ such that $S=\{P_1,P_2,\dots ,P_n\}$ $(n\ge 1)$, where $P_i$ $(1\le i\le n)$ belongs in $W$. We shall call $S$ a set of integer points.

Definition 3: Where $S$ is a set of integer points, if the points $R$ and $T$ belong to $S$, and there exists a finite sequence $Q_1,Q_2,\dots ,Q_k$ satisfying the following:

1. $Q_i$ belongs to $S$ $(1\le i\le k)$;
2. $Q_1=R,Q_k=T$;
3. $Q_i\sim Q_{i+1}$ $(1\le i\le k-1)$ — i.e. $Q_i$ and $Q_{i+1}$ are neighbors; and
4. $Q_i\ne Q_j$ for any $1\le i<j\le k$.

then we shall say that $R$ and $T$ are connected within set $S$, where the sequence $Q_1,Q_2,\dots ,Q_k$ shall be called a pathway connecting points $R$ and $T$.

Definition 4: For a set of integer points $V$, if for any two of $V$'s integer points there exists exactly one pathway connecting them, then $V$ shall be known as a singular set of integer points.

Definition 5: For any integer point on the plane, we can assign it an integer score. Thus, we shall call the sum of the scores of all the points in a set of integer points its total score.

Given a singular set of integer points $V$, we would like to find the optimally connected subset $B$, where:

1. $B$ is a subset of $V$;
2. any two integer points in $B$ are connected within $B$; and
3. out of the set of integer points satisfying 1. and 2., $B$ is the set where the total score is highest.

Input Specification

Line 1 contains an integer $N$ $(2\le N\le 1000)$, the number of points in $V$. Within the following $N$ lines, the $i$-th line $(1\le i\le N)$ contains three space-separated integers $X_i$, $Y_i$, and $C_i$ $(-{10}^6\le X_i,Y_i\le {10}^6;-100\le C_i\le 100)$, representing the coordinates of the $i$-th point along with its score.

Output Specification

The output should consist of one integer, the total score of the optimally connected subset.

Sample Input

5
0 0 -2
0 1 1
1 0 1
0 -1 1
-1 0 1

Sample Output

2

Problem translated to English by Alex.