ADAKOHL  Ada and Kohlrabi
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 testcases (anyway note that for biggest testcases there will be only 1 testcase).
The first line of each testcase contains 0 < N ≤ 3000 , the number of kohlrabi.
The next N lines contains three integers x, y, q: 10^{9} ≤ x, y ≤ 10^{9}, 10^{4} ≤ q ≤ 10^{4}, the coordinates of kohlrabi and its quality (note that no two kohlrabil will grow on same coordinates).
Output
For each testcase, 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:
20170913 22:49:52
@Morass Ok. I got it. Thank you. 

morass:
20170913 18:13:45
@julkas: Good day to you,


julkas:
20170913 15:23:39
@Morass Can you check my logic? Please. 

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


shubham_001:
20170912 07:18:57
@Blue.Mary will O(n^2) work here?


[Rampage] Blue.Mary:
20170907 06:34:55
[Deleted after AC.]

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