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 contains 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 kohlrabi will grow on same coordinates).

Output

For each test-case, print the best achievable 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

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

hide comments
2024-02-05 15:46:06
Wa on test case 13 , any hint?
2022-07-13 01:56:22 David
First Java solution!
2021-05-19 15:37:10 Harshal Paunikar
I am getting TLE. Here is my code - <snip>
I think it is O(n^2) and should have run.
Can someone please help me out?

Last edit: 2022-06-26 22:20:19
2017-09-13 22:49:52
@Morass Ok. I got it. Thank you.
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 ^_^
2017-09-13 15:23:39
@Morass Can you check my logic? Please.
2017-09-12 13:35:18
@Blue.Mary are you talking about log n factor due to use of std::map container?
2017-09-12 07:18:57
@Blue.Mary will O(n^2) work here?
2017-09-07 06:34:55 [Rampage] Blue.Mary
[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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.