Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
てんぷら君は果物を 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