18590번 - Snowy Smile 다국어

There are n pirate chests buried in Byteland, labeled by 1, 2, . . . , n. The i-th chest is located at point (x_i, y_i) on the plane, and its value is w_i. Note that w_i can be negative since the pirate can put some poisonous gases into the chest. When you open the i-th pirate chest, you will get wi value.

You want to make money from these pirate chests. You can select a rectangle such that its sides are all parallel to the coordinate axes, and then open all the chests inside this rectangle or on its border. Note that you must open all the chests within that range regardless of whether their values are positive or negative. But you can choose a rectangle with nothing in it to get a zero sum.

Please write a program to find the maximum total value of a rectangle.

The first line of the input contains an integer T (1 ≤ T ≤ 100), denoting the number of test cases.

Each test case starts with a line containing an integer n (1 ≤ n ≤ 2000), denoting the number of pirate chests.

Each of the next n lines contains three integers, x_i, y_i, and w_i (−10⁹ ≤ x_i, y_i, w_i ≤ 10⁹), describing the i-th pirate chest.

It is guaranteed that the sum of n in all test cases is at most 10 000.

For each test case, print a single line containing a single integer: the maximum total value.