JOI 王国は金の産出で有名である．JOI 王国では，毎年 1 回，ブルドーザーを用いて金を採掘する．

JOI 王国の土地は $xy$ 座標をもつ平面として表される．土地には $N$ 個の地点がある．$i$ 番目の地点（$1 \le i \le N$）は $(X_i, Y_i)$ である．各地点には金または岩のいずれか一方があり，両方はない．

地点 $i$ に金があるとき，そこを 1 回採掘すると，価値 $V_i$ の金が得られる．地点 $i$ に岩があるとき，そこを 1 回採掘すると，岩が得られる．それを処分するための費用は $C_i$ である．

採掘には次のようにブルドーザーを用いる．まず，$xy$ 平面上の平行な 2 直線を選ぶ．次に，その平行な 2 直線の間の領域にある（2 直線上にある金や岩も含む）すべての金と岩を，それぞれ 1 回ずつ採掘する．

JOI 王国の利益は，採掘領域内の金の価値の合計から，同じ領域内の岩を処分する費用の合計を引いた値である．JOI 王国の利益を最大化したい．

課題

JOI 王国の利益の最大値を求めるプログラムを作成せよ．

入力

標準入力から以下のデータを読み込め．

• 入力の 1 行目には，金または岩を採取できる地点の個数を表す整数 $N$ が書かれている．

• 続く $N$ 行のうちの $i$ 行目（$1 \le i \le N$）には，空白を区切りとして 3 個の整数 $X_i, Y_i, W_i$ が書かれている．

  • $W_i \ge 1$ のとき，$i$ 番目の地点 $(X_i, Y_i)$ には金がある．そこを 1 回採掘すると，価値 $V_i = W_i$ の金が得られる．
  • $W_i \le -1$ のとき，$i$ 番目の地点 $(X_i, Y_i)$ には岩がある．そこを 1 回採掘すると，岩が得られ，それを処分する費用は $C_i = -W_i$ である．

  $W_i \neq 0$ が成り立つ．

出力

標準出力に 1 行で出力せよ．出力には JOI 王国の利益の最大値を含めよ．

制約

すべての入力データは以下の条件を満たす．

• $1 \le N \le 2\,000$．
• $-1\,000\,000\,000 \le X_i \le 1\,000\,000\,000$（$1 \le i \le N$）．
• $-1\,000\,000\,000 \le Y_i \le 1\,000\,000\,000$（$1 \le i \le N$）．
• $1 \le |W_i| \le 1\,000\,000\,000$．
• $(X_i, Y_i) \neq (X_j, Y_j)$（$1 \le i < j \le N$）．

小課題

小課題は 5 つある．各小課題の配点および追加の制約は以下の通りである：

小課題 1 [5 点]

• $N \le 100$．
• $Y_i = 0$（$1 \le i \le N$）．言い換えると，すべての地点は $x$ 軸上にある．

小課題 2 [20 点]

• $N \le 100$．
• 相異なる 3 個の地点が同一直線上にあることはない．
• $L$ を相異なる 2 個の地点を通る $xy$ 平面上の直線とする．$L'$ を相異なる 2 個の地点を通る，$L$ とは異なる $xy$ 平面上の別の直線とする．このとき，$L$ と $L'$ は互いに平行でない．

小課題 3 [35 点]

• 相異なる 3 個の地点が同一直線上にあることはない．
• $L$ を相異なる 2 個の地点を通る $xy$ 平面上の直線とする．$L'$ を相異なる 2 個の地点を通る，$L$ とは異なる $xy$ 平面上の別の直線とする．このとき，$L$ と $L'$ は互いに平行でない．

小課題 4 [20 点]

• 相異なる 3 個の地点が同一直線上にあることはない．

小課題 5 [20 点]

追加の制約はない．

入出力例

入力 1

5
-5 5 -2
2 5 10
1 4 -2
4 -5 4
-2 2 7

出力 1

19

注記

入力例 1 において，JOI 王国における金（Gold）と岩（Rock）の位置は以下の通りである．

この入力例では，地点 $2, 3, 4, 5$ にある金や岩を採取することができる．このとき JOI 王国の利益は $19$ となる．これが JOI 王国の利益の最大値である．

入力 2

6
0 0 6
1 0 -2
2 0 8
0 1 -2
1 1 5
2 1 -2

出力 2

15

注記

入力例 2 において，地点 $1, 2, 3$ は同一直線上にある．また，地点 $4, 5, 6$ も同一直線上にある．

入力 3

5
0 0 2
4 0 2
3 2 -1
1 2 2
1 1 -1

出力 3

5

注記

入力例 3 において，相異なる 3 個の地点が同一直線上にあることはない．地点 $1$ と地点 $2$ を通る直線を $L$ とし，地点 $3$ と地点 $4$ を通る直線を $L'$ とする．このとき，$L$ と $L'$ は互いに平行である．

入力 4

2
0 0 -1
1 0 -1

出力 4

0

注記

金も岩もまったく含まない領域を選ぶことも可能である．入力例 4 において，利益の最大値は $0$ である．

入力 5

15
10 3 30
5 10 -17
4 -5 14
0 -3 -9
-2 3 17
6 9 -19
-9 -6 -14
-2 -3 10
-3 -3 30
8 1 -28
9 -9 -5
7 -5 -24
-8 -10 5
-7 2 20
10 -3 -13

出力 5

107