Starry Night Camping

Description:

Input:

The first line contains a single integer $$$n$$$ ($$$1\leq n\leq 1\,000$$$), representing the number of tents.

Each of the next $$$n$$$ lines contains three integers $$$x_i$$$, $$$y_i$$$ and $$$w_i$$$ ($$$-10^9\leq x_i,y_i \leq 10^9$$$, $$$1\leq w_i\leq 10^9$$$), representing the coordinate of the $$$i$$$-th tent and its weight. No two tents are located at the same point.

Output:

A single integer — the maximum sum of the weights of the remaining tents.

Sample Input:

5
0 0 4
0 1 5
1 0 3
1 1 1
-1 1 2

Sample Output:

12

Sample Input:

32
2 2 1
2 3 1
3 2 1
3 3 1
2 6 1
2 5 1
3 6 1
3 5 1
2 8 1
2 9 1
1 8 1
1 9 1
2 12 1
2 11 1
1 12 1
1 11 1
6 2 1
7 2 1
6 3 1
5 3 1
6 6 1
7 6 1
5 5 1
6 5 1
6 8 1
5 8 1
6 9 1
7 9 1
6 12 1
5 12 1
6 11 1
7 11 1

Sample Output:

24

Note:

Here is an illustration of the second example. Black triangles indicate the important tents. This example also indicates all $$$8$$$ forbidden patterns.