National Olympiad in Informatics, China, 1999
It is well-known that we can uniquely represent any point on the Cartesian coordinate system using an ordered pair . If both and are integers, then we shall call an integer point, otherwise we shall call a non-integer point. We shall denote all integer points on the plane using the set .
Definition 1: For two points , if , then and shall be considered neighbors, which is denoted as . Otherwise, and are considered non-neighboring.
Definition 2: The set is a finite subset of such that , where belongs in . We shall call a set of integer points.
Definition 3: Where is a set of integer points, if the points and belong to , and there exists a finite sequence satisfying the following:
- belongs to ;
- ;
- — i.e. and are neighbors; and
- for any .
then we shall say that and are connected within set , where the sequence shall be called a pathway connecting points and .
Definition 4: For a set of integer points , if for any two of 's integer points there exists exactly one pathway connecting them, then 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 , we would like to find the optimally connected subset , where:
- is a subset of ;
- any two integer points in are connected within ; and
- out of the set of integer points satisfying 1. and 2., is the set where the total score is highest.
Input Specification
Line 1 contains an integer , the number of points in . Within the following lines, the -th line contains three space-separated integers , , and , representing the coordinates of the -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 .
Comments