ADAKOHL - Ada and Kohlrabi

no tags 

As you might already know, Ada the Ladybug is a farmer. She has a garden with kohlrabi. Each kohlrabi has assigned a quality, which is a number (possibly negative, since the kohlrabi might be rotten).

Ada wants to gather some kohlrabi so she wants to pick a line such that the sum of kohlrabi on the line is maximal. Can you help her to find such line?

Input

The first line of input containts 1 ≤ T ≤ 100 , the number of test-cases (anyway note that for biggest test-cases there will be only 1 test-case).

The first line of each test-case contains 0 < N ≤ 3000 , the number of kohlrabi.

The next N lines contains three integers x, y, q: -109 ≤ x, y ≤ 109, -104 ≤ q ≤ 104, the coordinates of kohlrabi and its quality (note that no two kohlrabil will grow on same coordinates).

Output

For each test-case, print the best achieavable sum of qualities of kohlrabies on a single line.

Example Input

5
4
0 0 1
1 1 1
2 2 1
3 3 1
5
0 0 -10
1 0 2
0 1 3
-1 0 2
0 -1 3
3
0 0 -1
1 1 -2
1 3 -5
2
0 0 666
1 7 -666
5
0 0 1
99999999 0 6
0 99999999 5
-99999999 0 6
0 -99999999 5

Example Output

4
5
0
666
13

Example Input 2

1
7
10 8 -2
9 4 -1
-3 -5 -5
7 5 1
-3 2 -6
5 10 -4
9 7 10

Example Output 2

10

Example Input 3

1
4
-6 0 9
7 4 7
7 -6 -10
-6 7 10

Example Output 3

19

Example Input 4

1
6
-10 -1 -10
8 3 4
0 9 -2
4 -6 1
6 0 10
-6 1 -10

Example Output 4

14

hide comments
julkas: 2017-09-13 22:49:52

@Morass Ok. I got it. Thank you.

morass: 2017-09-13 18:13:45

@julkas: Good day to you,

please take look at third (new) smple ... (locally) your program outputs 17, yet imho 19 shall be the right answer. (1s and 4th points are above each other ... so are 2nd and 3rd)

Hope it helped

Have Nice Day ^_^

julkas: 2017-09-13 15:23:39

@Morass Can you check my logic? Please.

shubham_001: 2017-09-12 13:35:18

@Blue.Mary are you talking about log n factor due to use of std::map container?

shubham_001: 2017-09-12 07:18:57

@Blue.Mary will O(n^2) work here?

[Rampage] Blue.Mary: 2017-09-07 06:34:55

[Deleted after AC.]

@shubham_001: The complexity of my program is indeed O(n^2), but pay attention to the (hidden?) constant factor.

Last edit: 2017-09-12 09:22:36

Added by:Morass
Date:2017-09-07
Time limit:4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All