Optimal Connected Subset
- A point P(x,y) is called an integer point if and only if both x and y are integers.
- W is the set which contains all the integer points on the plane.
- Two integer point P(x,y) and Q(x',y') are called adjacent if and only if |x-x'|+|y-y'|=1.
- S is a set of integer points if and only if S is a limited subset of W.
-
If S is a set of integer points, R and T belong to S,and there exist a limited integer point sequence Q0(=R),Q1,Q2,...,Qk,Qk+1(=T) which satisfies that
we call R and T are connected and the sequence Qi(0<=i<=k) is a path that connect R and T.
- Qi!=Qj iff i!=j
- Qi and Qi+1 are adjacent, for each 0<=i<=k.
- Qi belongs to S, for each 0<=i<=k+1.
- If S is a set of integer points, X and Y are some integer points that belong to S, there exists one and only one path connected X and Y, then S is called an optimal set.
Given an optimal set V, your task is to find an optimal set B, satisfying that B is a subset of V and the sum of the weights of each integer point is maximum.
Input
The very first line of the input contains a single integer T, the number of test cases. T blocks follow.
For each test case, the first line contains a single integer N=|V|(N<=1000). N lines follow, each contains 3 integers, the X-coordinate, the Y-coordinate and the weight(the absolute value of the weight<=100) of the ith integer point, separated by single spaces.
Output
T lines,each contains a single integer - the maximum sum of weights.
Example
Input: 1 5 0 0 -2 0 1 1 1 0 1 0 -1 1 -1 0 1</p>Output: 2