JOI, who has become a professional home gardener, grows plants called IOI-grass in his field every year. When he sows the seeds of IOI-grass in winter, they sprout in spring and grow to a fixed height. Some IOI-grass plants bear beautiful fruits in autumn. IOI-grass plants that bear fruit are harvested. IOI-grass plants that do not bear fruit wither in winter.

JOI's field is divided into $N$ plots arranged in an east-west direction. In the $i$-th plot from the west ($1 \le i \le N$), an IOI-grass plant $i$ is planted. In spring, IOI-grass $i$ grows to a height of $H_i$ and does not grow any further. If IOI-grass $i$ bears fruit, it is traded for $P_i$ yen. IOI-grass that does not bear fruit has no commercial value.

In spring, JOI went to check on his field and decided to maximize the profit obtained from trading IOI-grass by pulling out some of the planted IOI-grass plants. Pulling out IOI-grass $i$ ($1 \le i \le N$) costs $C_i$ yen. Pulled-out IOI-grass withers. IOI-grass can only be pulled out in spring; it cannot be pulled out in summer or autumn.

IOI-grass is a plant that requires a lot of sunlight in summer. For an IOI-grass plant in a certain plot, if there is an IOI-grass plant taller than it planted in summer in both a plot with a smaller index and a plot with a larger index, that IOI-grass plant will not bear fruit in autumn. In other words, when IOI-grass $i$ ($1 \le i \le N$) has not been pulled out, it bears fruit in autumn if and only if there is no IOI-grass taller than IOI-grass $i$ in plots $1, \dots, i-1$ at the summer stage, or there is no IOI-grass taller than IOI-grass $i$ in plots $i+1, \dots, N$ at the summer stage.

JOI's profit is the total trading price of the IOI-grass that bore fruit minus the total cost of pulling out the IOI-grass. How much profit can JOI obtain from the IOI-grass?

Task

Given the information about JOI's field and the IOI-grass planted in the field, write a program to calculate the maximum profit JOI can obtain.

Input

Read the following data from standard input:

• The first line contains an integer $N$, representing the number of plots in JOI's field.
• The following $N$ lines, the $i$-th line ($1 \le i \le N$), contains three space-separated integers $H_i$, $P_i$, and $C_i$. This indicates that IOI-grass $i$ grows to a height of $H_i$ in spring, its trading price if it bears fruit in autumn is $P_i$ yen, and the cost to pull it out is $C_i$ yen.

Output

Output the maximum profit JOI can obtain as an integer on a single line.

Constraints

All input data satisfies the following conditions:

• $3 \le N \le 100\,000$.
• $1 \le H_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $1 \le P_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $1 \le C_i \le 1\,000\,000\,000$ ($1 \le i \le N$).

Subtasks

1. (10 points) $N \le 20$ is satisfied.
2. (10 points) $N \le 300$ is satisfied.
3. (10 points) $N \le 5\,000$ is satisfied.
4. (50 points) $H_i \neq H_j$ ($1 \le i < j \le N$) is satisfied.
5. (20 points) No additional constraints.

Examples

Input 1

7
22 60 30
46 40 30
36 100 50
11 140 120
38 120 20
24 90 60
53 50 20

Output 1

320

Note 1

Consider the state after pulling out IOI-grass 2 and IOI-grass 7. The remaining IOI-grass plants are as follows:

The trading prices of IOI-grass 1, 3, 5, and 6 are 60 yen, 100 yen, 120 yen, and 90 yen, respectively. The costs to pull out IOI-grass 2 and 7 are 30 yen and 20 yen, respectively. JOI's profit is $60 + 100 + 120 + 90 - 30 - 20 = 320$ yen, which is the maximum value.

Input 2

5
18 150 180
18 380 250
18 140 170
17 180 900
14 150 520

Output 2

1000

Note 2

In this example, there is no need to pull out any IOI-grass, and all IOI-grass plants bear fruit in autumn.

Input 3

8
52 156 59
15 166 185
16 122 115
24 161 154
44 252 678
32 225 557
44 155 254
59 57 253

Output 3

854