Description

众所周知，我们可以通过直角坐标系把平面上的任何一个点 $P$ 用一个有序数对 $(x,y)$ 来唯一表示，如果 $x,y$ 都是整数，我们就把点 $P$ 称为整点，否则点 $P$ 称为非整点。我们把平面上所有整点构成的集合记为 $W$。

定义 1 ：两个整点 $P_1(x_1,y_1),P_2(x_2,y_2)$，若 $|x_1-x_2|+|y_1-y_2|=1$，则称 $P_1,P_2$ 相邻，记作 $P_1$~$P_2$ ，否则称 $P_1,P_2$ 不相邻。

定义 2 ：设点集 $S$ 是 $W$ 的一个有限子集，即 $S$=$\{P_1,P_2,…,P_n\}$ $(n \ge 1)$，其中 $P_i (1 \le i \le n)$ 属于 $W$，我们把 $S$ 称为整点集。

定义 3 ：设 $S$ 是一个整点集，若点 $R$,$T$ 属于 $S$ ，且存在一个有限的点序列 $Q_1,Q_2,…,Q_k$ 满足:

1. $Q_i$ 属于 $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)$，即 $Q_i$ 与 $Q_{i+1}$ 相邻;
4. 对于任何 $1 \le i \le j \le k$ 有 $Q_i≠Q_j$;

我们则称点 $R$ 与点 $T$ 在整点集 $S$ 上连通，把点序列 $Q_1,Q_2,…,Q_k$ 称为整点集 $S$ 中连接点 $R$ 与点 $T$ 的一条道路。

定义 4 ：若整点集 $V$ 满足：对于 $V$ 中的任何两个整点， $V$ 中有且仅有一条连接这两点的道路，则 $V$ 称为单整点集。

定义 5 ：对于平面上的每一个整点，我们可以赋予它一个整数，作为该点的权，于是我们把一个整点集中所有点的权的总和称为该整点集的权和。

我们希望对于给定的一个单整点集 $V$ ，求出一个 $V$ 的最优连通子集 $B$ ，满足：

1. $B$ 是 $V$ 的子集
2. 对于 $B$ 中的任何两个整点，在 $B$ 中连通；
3. $B$ 是满足条件 (1) 和 (2) 的所有整点集中权和最大的。

Format

Input

第1行是一个整数N，表示单整点集V中点的个数； 以下N行中，第i行(1<=i<=N)有三个整数，$X_i$ ,$Y_i$ ,$C_i$依次表示第i个点的横坐标，纵坐标和权。同一行相邻两数之间用一个空格分隔。

Output

仅一个整数，表示所求最优连通集的权和。

Samples

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

2

Limitation

参数约定

2<=N<=1000 -$10^6$<=$X_i$ ,$Y_i$ <=$10^6$ -100<=$C_i$ <=100