Growing Vegetables is Fun 2

JOI, now a professional home gardener, grows IOI grass every year in his own field. He sows seeds in winter, and in spring they sprout and grow to a fixed height. Some IOI grass plants bear beautiful fruit in autumn. A plant that bears fruit is harvested. A plant that does not bear fruit dies in winter.

JOI's field is divided into $N$ plots arranged from west to east. Plot $i$ holds IOI grass $i$. In spring, IOI grass $i$ grows to height $H_i$ and then stops growing. If IOI grass $i$ bears fruit, it sells for $P_i$ yen. IOI grass that does not bear fruit has no commercial value.

When JOI checks the field in spring, he may pull up some of the IOI grass to maximize his profit from sales. Pulling up IOI grass $i$ (1 $\le$ $i$ $\le$ $N$) costs $C_i$ yen. Pulled-up plants die. IOI grass can only be pulled up in spring, not in summer or autumn.

IOI grass needs a lot of sunlight in summer. Suppose a plant in some plot has a taller IOI grass planted in summer both on the plots with smaller numbers and on the plots with larger numbers. Then that plant does not bear fruit in autumn. In other words, if IOI grass $i$ (1 $\le$ $i$ $\le$ $N$) is not pulled up, it bears fruit in autumn only if no IOI grass taller than IOI grass $i$ is in plots $1, \ldots, i-1$ during summer, or no IOI grass taller than IOI grass $i$ is in plots $i+1, \ldots, N$ during summer.

Profit is the total sales price of the fruiting IOI grass minus the total cost of pulling up plants. What is the maximum profit JOI can earn from the IOI grass?

Given the information about the field and the IOI grass planted in it, write a program that finds the maximum profit JOI can earn.

The first line contains an integer $N$, the number of plots in JOI's field.

Each of the next $N$ lines contains three integers $H_i$, $P_i$, and $C_i$, separated by spaces, for $1 \le i \le N$. This means that IOI grass $i$ grows to height $H_i$ in spring, sells for $P_i$ yen if it bears fruit in autumn, and costs $C_i$ yen to pull up.

Print the maximum profit JOI can earn as one integer on a single line.

• $3 \le N \le 100000$
• $1 \le H_i \le 1000000000$ for $1 \le i \le N$
• $1 \le P_i \le 1000000000$ for $1 \le i \le N$
• $1 \le C_i \le 1000000000$ for $1 \le i \le N$