配点 : 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