AT_cpsco2019_s1_f.Fruits in Season

てんぷら君有 $N$ 个水果，他打算在未来的 $N$ 天内把它们全部吃掉。

每天，他会从剩下的水果中挑选一个来吃，并且必须在当天就吃完。每个水果 $i$ 都有一个最佳食用日期 $t_i$，而实际吃掉水果的那天与这个最佳日期的偏差，会影响它的美味程度。

具体来说，如果在第 $t_i$ 天吃掉水果 $i$，其美味程度为 $A_i$。如果偏离了最佳日期 $t_i$ 天，那么美味程度将会因为每天的偏离减少 $B_i$。即，如果在第 $j$ 天（$1 \le j \le N$）吃掉水果 $i$（$1 \le i \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 \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$ 天吃水果 $2$，美味程度为 $6 - |1 - 1| \times 3 = 6$。
• 第 $2$ 天吃水果 $3$，美味程度为 $5 - |2 - 2| \times 2 = 5$。
• 第 $3$ 天吃水果 $1$，美味程度为 $7 - |3 - 1| \times 1 = 5$。

在这种情况下，满意度为 $5$，这是可能达到的最大满意度。

本翻译由 AI 自动生成