問題文

てんぷら君は果物を 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
• 入力はすべて整数

入力例 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