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 1\,000)~, 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.