问题

天妃拉酱有$N$个水果。从今天开始，他决定在连续的$N$天里吃完所有的水果。

每天他会从剩下的水果中选择一个吃掉。吃过一次的水果当天就会被完全吃掉。

水果$i$有一个旬$T_i$，根据旬和吃水果的日期，水果的美味程度会发生变化。

如果在第$T_i$天吃水果$i$，那么它的美味程度为$A_i$，随着天数的增加，每隔一天吃该水果的美味程度会下降$B_i$。更准确地说，水果$i$（$1\le i\le N$）在第$j$天（$1\le j\le N$）吃的美味程度可以表示为$A_i -|j-T_i|\times B_i$。

他的满足度是吃水果的美味程度的最小值。

请计算出当天妃拉酱以适当的顺序吃水果时，他能得到的最大满足度。

约束条件

• $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

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