Gold Mines

A country is nicknamed the land of gold. Many of its gold mines are still undeveloped. On a map each gold mine is drawn as a point in the plane.

Figure 1

Each point $p_i$ carries an integer $w_i$ that is positive or negative. $w_i$ is the profit or the loss produced by developing that mine. If $w_i$ is positive, developing the mine earns $w_i$. If $w_i$ is negative, developing the mine costs $|w_i|$.

A mine developer buys a rectangular plot $R$ whose sides are parallel to the $x$ axis and the $y$ axis, then develops every mine contained in $R$. A mine lying on a side of the rectangle counts as contained in $R$. The development profit is the sum of $w_i$ over the mines contained in $R$.

The developer looks for the rectangle $R$ with the largest development profit. For the mines in Figure 1, the region with the largest development profit is the one drawn in Figure 2, and that profit is 7.

Given the coordinates of the gold mines and the profit or loss of developing each one, write a program that prints the largest development profit obtainable by buying one rectangular plot.

Figure 2

The first line contains the number of gold mines $N$ ($1 \le N \le 3000$). Each of the next $N$ lines contains two non-negative integers $x$ and $y$ ($0 \le x, y \le 10^9$) giving the coordinates of a mine, and an integer $w$ ($-10^9 \le w \le 10^9$) giving the profit or the loss of developing it, separated by spaces. All mine coordinates are distinct, and at least one mine has $w > 0$.

Print on one line the largest development profit the developer can obtain by buying a rectangular plot $R$. The value can exceed the range of a 32-bit integer during the computation, so you may need a 64-bit integer type.