题目描述

家庭菜园的专家 JOI 君，每年都会在自己的园圃中种植一种名为 IOI 草的植物。冬季时，他播种 IOI 草的种子，春季时种子发芽并生长至固定高度。到了秋季，一些 IOI 草会结出美丽的果实，而未结果的 IOI 草则会在冬季枯萎。

JOI 君的园圃被划分为 $N$ 个东西方向排列的区域，从西到东第 $i$ 个区域（$1 \le i \le N$）种植着 IOI 草 $i$。IOI 草 $i$ 在春季会生长至高度 $H_i$，之后不再生长。如果 IOI 草 $i$ 结出了果实，则在秋季可以以 $P_i$ 日元的价格出售；若未结果，则其商业价值为零。

到了春季，观察园圃情况的 JOI 君决定拔除部分 IOI 草，以最大化通过拔除所得的收益。拔除 IOI 草 $i$（$1 \le i \le N$）需要花费 $C_i$ 日元。被拔除的 IOI 草会枯死，且只能在春季拔除，夏季或秋季均不可拔除。

IOI 草是一种在夏季需要大量阳光的植物。对于某个区域内种植的 IOI 草，如果在其左侧（编号更小的区域）和右侧（编号更大的区域）都存在比它更高（高度大于 $H_i$）的 IOI 草，则该 IOI 草在秋季无法结果。换句话说，IOI 草 $i$（$1 \le i \le N$）在秋季能结果的条件是：在夏季阶段，区域 $1$ 至区域 $i-1$ 中没有比 IOI 草 $i$ 更高的 IOI 草，或区域 $i+1$ 至区域 $N$ 中没有比 IOI 草 $i$ 更高的 IOI 草。

JOI 君的收益等于所有结果 IOI 草的出售价格总和减去拔除所有 IOI 草所花费的总费用。问题是：JOI 君最多可以获得多少收益？

题目

给定 JOI 君的园圃信息及种植的 IOI 草信息，编写程序求出 JOI 君能获得的最大收益。

输入格式

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

• 第一行包含一个整数 $N$，表示 JOI 君园圃的区域数量。
• 接下来的 $N$ 行，第 $i$ 行（$1 \le i \le N$）包含三个整数 $H_i, P_i, C_i$，以空格分隔。这表示 IOI 草 $i$ 在春季生长至高度 $H_i$，秋季结果时的售价为 $P_i$ 日元，拔除它需要花费 $C_i$ 日元。

输出格式

在标准输出上，输出 JOI 君的最大收益，以一个整数形式输出在一行中。

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

320

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

1000

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

854

提示

样例 1 解释

考虑 IOI 草 2 和 IOI 草 7 被拔去的情况。剩下的 IOI 草如下表所示：

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

IOI 草的编号	1	3	4	5	6
IOI 草的高度	22	36	11	38	24
秋季是否结果	○		×	○

IOI 草 1、IOI 草 3、IOI 草 5、IOI 草 6 的出售价格分别为 60 日元、100 日元、120 日元、90 日元。拔除 IOI 草 2 和 IOI 草 7 的费用分别为 30 日元和 20 日元。JOI 君的收益为 $60 + 100 + 120 + 90 - 30 - 20 = 320$ 日元，此值即为最大值。

数据范围

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

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

子任务

子任务 1 [10 分]

• $N \le 20$

子任务 2 [10 分]

• $N \le 300$

子任务 3 [10 分]

• $N \le 5000$

子任务 4 [50 分]

• $H_i \ne H_j$（$1 \le i < j \le N$）

子任务 5 [20 分]

• 无额外限制

翻译由 Qwen3-235B 完成