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.