Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
 Register new ID

Snowy Smile

Time Limit: 4000/4000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 4624    Accepted Submission(s): 1312

Problem Description
There are $n$ pirate chests buried in Byteland, labeled by $1,2,\dots,n$. The $i$-th chest's location is $(x_i,y_i)$, and its value is $w_i$, $w_i$ can be negative since the pirate can add some poisonous gases into the chest. When you open the $i$-th pirate chest, you will get $w_i$ value.

You want to make money from these pirate chests. You can select a rectangle, the sides of which are all paralleled to the axes, and then all the chests inside it or on its border will be opened. Note that you must open all the chests within that range regardless of 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 best rectangle with maximum total value.

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

In each test case, there is one integer $n(1\leq n\leq 2000)$ in the first line, denoting the number of pirate chests.

For the next $n$ lines, each line contains three integers $x_i,y_i,w_i(-10^9\leq x_i,y_i,w_i\leq 10^9)$, denoting each pirate chest.

It is guaranteed that $\sum n\leq 10000$.

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

Sample Input
2 4 1 1 50 2 1 50 1 2 50 2 2 -500 2 -1 1 5 -1 1 1

Sample Output
100 6


Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-04-15 23:56:17, Gzip enabled