Problem Description

Tempura-kun has $ N $ fruits. He decided to eat all of them over the next $ N $ days.

Every day, he chooses one of the remaining fruits to eat. Once he starts eating a fruit, he finishes it that day.

Each fruit $ i $ has a season $ t_i $, and the deliciousness of the fruit changes depending on the season and the date it is eaten.

The deliciousness of fruit $ i $ when eaten on day $ t_i $ is $ A_i $. The deliciousness decreases by $ B_i $ for each day deviation from the season day $ t_i $. More precisely, the deliciousness of fruit $ i $ $(1\le\ i\le\ N)$ when eaten on day $ j $ $(1\le\ j\le\ N)$ is $A_i\ -|j-t_i|\times\ B_i$.

His satisfaction is the minimum deliciousness of the fruits he eats over the $ N $ days.

Determine the maximum satisfaction Tempura-kun can achieve by optimally deciding the order in which he eats the fruits.

Input Format

The input is given from the standard input in the following format:

$ N $ $t_1\ A_1\ B_1$ $t_2\ A_2\ B_2$ $\vdots$ $t_N\ A_N\ B_N$

Output Format

Output the maximum satisfaction Tempura-kun can achieve in one line.

Sample Input and Output

Sample Input #1

3
1 7 1
1 6 3
2 5 2

Sample Output #1

5

Sample Input #2

2
2 0 1
2 0 1

Sample Output #2

-1

Sample Input #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

Sample Output #3

65

Notes/Hints

Constraints

• $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$
• All inputs are integers

Sample Explanation 1

If he eats fruit $ 2 $ on day $ 1 $, the deliciousness is $6-|1-1|\times\ 3\ =\ 6$. If he eats fruit $ 3 $ on day $ 2 $, the deliciousness is $5-|2-2|\times\ 2\ =\ 5$. If he eats fruit $ 1 $ on day $ 3 $, the deliciousness is $7-|3-1|\times\ 1\ =\ 5$. The satisfaction is $ 5 $, which is the maximum.

见题面 Input 部分

见题面 Output 部分