AT_cpsco2019_s1_f Fruits in Season

[problemUrl]: https://atcoder.jp/contests/cpsco2019-s1/tasks/cpsco2019_s1_f てんぷら君は果物を $ 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 $ 日間で食べた果物の美味しさの最小値です。 てんぷら君が食べる順番を適切に決めたときの、得られる満足度の最大値を求めてください。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ t_1\ A_1\ B_1 $ $ t_2\ A_2\ B_2 $ $ \vdots $ $ t_N\ A_N\ B_N $

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

### 制約 - $ 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 $ - 入力はすべて整数 ### Sample Explanation 1 $ 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 $ で、これが最大です。