F - Fruits in Season

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600

問題文

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

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

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

果物 it_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