Description

As is well known, we can use the Cartesian coordinate system to uniquely represent any point $P$ on the plane by an ordered pair $(x,y)$. If both $x,y$ are integers, then we call point $P$ a lattice point; otherwise, point $P$ is a non-lattice point. Let the set of all lattice points on the plane be denoted by $W$.

Definition 1: For two lattice 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$ are said to be adjacent, denoted by $P_1$~$P_2$. Otherwise, they are said to be non-adjacent.

Definition 2: Let a point set $S$ be a finite subset of $W$, that is, $S=\{P_1,P_2,\ldots,P_n\}$ $(n \ge 1)$, where $P_i$ $(1 \le i \le n)$ belongs to $W$. We call $S$ a lattice point set.

Definition 3: Let $S$ be a lattice point set. If points $R$ and $T$ belong to $S$, and there exists a finite point sequence $Q_1,Q_2,\ldots,Q_k$ satisfying:

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

then we say point $R$ and point $T$ are connected in the lattice point set $S$. The point sequence $Q_1,Q_2,\ldots,Q_k$ is called a path in $S$ connecting $R$ and $T$.

Definition 4: If a lattice point set $V$ satisfies that for any two lattice points in $V$, there exists one and only one path in $V$ connecting these two points, then $V$ is called a single lattice point set.

Definition 5: For each lattice point on the plane, we can assign it an integer as the weight of that point. The sum of the weights of all points in a lattice point set is called the weight sum of that set.

For a given single lattice point set $V$, we want to find an optimal connected subset $B$ of $V$ such that:

1. $B$ is a subset of $V$.
2. Any two lattice points in $B$ are connected within $B$.
3. Among all lattice point sets satisfying conditions (1) and (2), $B$ has the maximum weight sum.

Input Format

The first line contains an integer $N$, indicating the number of points in the single lattice point set $V$.

In the next $N$ lines, the $i$-th line $(1 \le i \le N)$ contains three integers $X_i,Y_i,C_i$, which represent the $x$-coordinate, $y$-coordinate, and weight of the $i$-th point, respectively. Adjacent numbers on the same line are separated by one space.

Output Format

Output one integer, the weight sum of the required optimal connected set.

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

2

Hint

Translated by ChatGPT 5