作为一名家庭菜园专家，JOI 君每年都在自己的田地里种植一种名为 IOI 草的植物。冬天播下 IOI 草的种子后，春天它们会发芽并长到固定的高度。一些 IOI 草在秋天会结出美丽的果实。结出果实的 IOI 草会被收获，而没有结出果实的 IOI 草则会在冬天枯萎。

JOI 君的田地被分成了东西向排列的 $N$ 个区域，从西边数第 $i$ 个区域 ($1 \le i \le N$) 种植着 IOI 草 $i$。IOI 草 $i$ 在春天会长到高度 $H_i$，之后便不再生长。如果 IOI 草 $i$ 结出了果实，其交易价格为 $P_i$ 日元。没有结出果实的 IOI 草则没有商业价值。

春天，JOI 君去视察田地时，决定通过拔掉一些已种植的 IOI 草，来最大化通过 IOI 草交易获得的利润。拔掉 IOI 草 $i$ ($1 \le i \le N$) 需要花费 $C_i$ 日元的费用。被拔掉的 IOI 草会枯萎。IOI 草只能在春天拔掉，夏天或秋天无法拔掉。

IOI 草是一种在夏天需要大量阳光的植物。对于某个区域种植的 IOI 草，如果其西侧（编号较小的区域）和东侧（编号较大的区域）在夏天都种植着比它更高的 IOI 草，那么该 IOI 草在秋天就不会结出果实。也就是说，当 IOI 草 $i$ ($1 \le i \le N$) 没有被拔掉时，它仅在以下情况之一时会在秋天结出果实：在夏天的阶段，区域 $1, \dots, i-1$ 中没有比 IOI 草 $i$ 更高的 IOI 草，或者区域 $i+1, \dots, N$ 中没有比 IOI 草 $i$ 更高的 IOI 草。

JOI 君的利润等于结出果实的 IOI 草的交易价格总和减去拔掉 IOI 草所花费的费用总和。请问 JOI 君最多能获得多少利润？

题目描述

给定 JOI 君的田地信息以及种植在田地里的 IOI 草的信息，编写一个程序来计算 JOI 君能获得的最大利润。

输入格式

从标准输入读取以下数据：

• 第 1 行包含一个整数 $N$，表示 JOI 君田地的区域数。
• 接下来的 $N$ 行中，第 $i$ 行 ($1 \le i \le N$) 包含三个整数 $H_i, P_i, C_i$，以空格分隔。这表示 IOI 草 $i$ 在春天会长到高度 $H_i$，秋天结出果实时的交易价格为 $P_i$ 日元，拔掉它所需的费用为 $C_i$ 日元。

输出格式

将 JOI 君能获得的最大利润作为一个整数输出到标准输出。

数据范围

所有输入数据满足以下条件：

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

子任务

1. (10 分) $N \le 20$
2. (10 分) $N \le 300$
3. (10 分) $N \le 5\,000$
4. (50 分) $H_i \neq H_j$ ($1 \le i < j \le N$)
5. (20 分) 无附加限制

样例

样例输入 1

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

样例输出 1

320

说明 1

考虑拔掉 IOI 草 2 和 IOI 草 7 后的状态。剩余的 IOI 草如下表所示：

IOI 草 1、3、5、6 的交易价格分别为 60 日元、100 日元、120 日元、90 日元。拔掉 IOI 草 2 和 7 的费用分别为 30 日元和 20 日元。JOI 君的利润为 $60 + 100 + 120 + 90 - 30 - 20 = 320$ 日元，这是最大值。

样例输入 2

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

样例输出 2

1000

说明 2

在此样例中，不需要拔掉任何 IOI 草，所有的 IOI 草在秋天都会结出果实。

样例输入 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

样例输出 3

854