010 - 投網

問題

イワシロ湖には魚が取れるポイントが$N$箇所ある。湖の上に座標平面を取ると、これらのポイントはすべて格子点、つまり、x座標とy座標がどちらも整数である点である。各ポイントに魚が何匹いるか漁師たちは把握している。

漁師のケンジロウ君は、イワシロ湖に正方形の網を投げて魚を捕る。網の一辺の長さは整数である。ケンジロウ君は、網の頂点が湖上の座標平面の格子点上に乗り、かつ、網の対角線の一本が直線$y=x$の上に乗るように網を投げなければならない。たとえば、右の図のAのように網を投げることはできるが、BやCのように投げることはできない。

ケンジロウ君は、辺も含めて網に覆われたポイントにいるすべての魚を捕ることができ、捕れた魚の数に応じた売り上げが得られる。しかし、網を作るコストは網の周の長さだけかかるため、ケンジロウ君が得られる利益は、捕れた魚の数から網の周の長さ（網の一辺の長さの４倍）を引いた値になる。

ケンジロウ君は、網の大きさと網を投げる位置をうまく決めて、網を1回だけ投げたときの利益が最大になるようにしたい。

魚がいるポイントの数と、各ポイントの位置とそこにいる魚の数が与えられたとき、網を1回だけ投げたときにケンジロウ君が得られる最大の利益を求めるプログラムを作成せよ。ただし、網の一辺の長さの最小値は1とする。

入力

入力は以下の形式で与えられる。

$N$
$x_1$ $y_1$ $f_1$
$x_2$ $y_2$ $f_2$
:
$x_N$ $y_N$ $f_N$

1行目に魚がいるポイントの数$N$ ($1 \leq N \leq 200,000=2\times10^5$)が与えられる。続く$N$行に、魚がいる$i$番目のポイントのx座標$x_i$とy座標 $y_i$ ($0 \leq x_i,y_i \leq 200,000=2\times10^5$)とそこにいる魚の数$f_i$ ($1 \leq f_i\leq 1,000,000,000=10^9$)が与えられる。ただし、同じ座標をもつポイントは与えられない($i \ne j$について、$x_i \ne x_j$または$y_i \ne y_j$）。

出力

ケンジロウ君が得られる最大の利益を１行に出力する。

入出力例

入力例１

3
3 2 1
4 5 1
5 3 9

出力例１

2

入力例２

1
0 0 1

出力例２

-3