問題文

てんぷら君は果物を $N$ 個持っています。今日から $N$ 日間ですべての果物を食べきることにしました。

彼は毎日、その時点で残っている果物から $1$ つを選んで食べます。$1$ 度食べた果物はその日のうちに完食します。

果物 $i$ には旬 $t_i$ が定められていて、旬とその果物を食べた日付によって美味しさが変化します。

果物 $i$ を $t_i$ 日目に食べた場合の美味しさは $A_i$ であり、$t_i$ 日目から $1$ 日ずれるごとに食べたときの美味しさが $B_i$ ずつ低くなります。 より正確には、果物 $i$ $(1\\le i\\le N)$ を $j$ 日目 $(1\\le j\\le N)$ に食べたときの美味しさは $A_i -|j-t_i|\\times B_i$ と表すことができます。

彼の得られる満足度は $N$ 日間で食べた果物の美味しさの最小値です。

てんぷら君が食べる順番を適切に決めたときの、得られる満足度の最大値を求めてください。

制約

• $1\\le N\\le 2\\times 10^4$
• $1\\le t_i\\le N$
• $0\\le A_i\\le 10^9$
• $1\\le B_i\\le 5\\times 10^4$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

$N$ $t_1\\ A_1\\ B_1$ $t_2\\ A_2\\ B_2$ $\\vdots$ $t_N\\ A_N\\ B_N$

出力

てんぷら君の得られる満足度の最大値を $1$ 行に出力してください。

入力例 1

3
1 7 1
1 6 3
2 5 2

出力例 1

5

$1$ 日目に果物 $2$ を食べると美味しさは $6-|1-1|\\times 3 = 6$ です。

$2$ 日目に果物 $3$ を食べると美味しさは $5-|2-2|\\times 2 = 5$ です。

$3$ 日目に果物 $1$ を食べると美味しさは $7-|3-1|\\times 1 = 5$ です。

このとき満足度は $5$ で、これが最大です。

入力例 2

2
2 0 1
2 0 1

出力例 2

-1

満足度が負になることもあります。

入力例 3

10
3 78 4
1 97 8
4 93 7
1 72 5
5 81 6
9 70 9
2 72 3
6 84 5
5 83 9
3 79 2

出力例 3

65