### National Olympiad in Informatics, China, 1999

## Day 2, Problem 2 - Optimally Connected Subset

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`), if |

_{2}`x`−

_{1}`x`| + |

_{2}`y`−

_{1}`y`| = 1, then

_{2}`P`and

_{1}`P`shall be considered

_{2}**neighbors**, which is denoted as

`P`~

_{1}`P`. Otherwise,

_{2}`P`and

_{1}`P`are considered non-neighboring.

_{2}Definition 2: The set `S` is a finite subset of `W` such that `S` = {`P _{1}`,

`P`, …,

_{2}`P`} (

_{n}`n`≥ 1), where

`P`(1 ≤

_{i}`i`≤

`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}`Q`satisfying the following:

_{k}`Q`belongs to_{i}`S`(1 ≤`i`≤`k`);`Q`=_{1}`R`,`Q`=_{k}`T`;`Q`~_{i}`Q`(1 ≤_{i+1}`i`≤`k`−1) — i.e.`Q`and_{i}`Q`are neighbours; and_{i+1}`Q`≠_{i}`Q`for any 1 ≤_{j}`i`<`j`≤`k`

then we shall say that `R` and `T` are **connected** within set `S`, where the sequence `Q _{1}`,

`Q`, …,

_{2}`Q`shall be called a

_{k}**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:

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

### Input Format

Line 1 contains an integer `N` (2 ≤ `N` ≤ 1000), the number of points in `V`. Within the following `N` lines, the `i`-th line (1 ≤ `i` ≤ `N`) contains three space-separated integers `X _{i}`,

`Y`, and

_{i}`C`(−10

_{i}^{6}≤

`X`,

_{i}`Y`≤ 10

_{i}^{6}; −100 ≤

`C`≤ 100), representing the coordinates of the

_{i}`i`-th point along with its score.

### Output Format

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

All Submissions

Best Solutions

**Point Value:** 15 (partial)

**Time Limit:** 1.00s

**Memory Limit:** 16M

**Added:** May 04, 2014

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...