P14407 [JOISC 2015] 有趣的家庭菜园 2 / Growing Vegetables is Fun 2

家庭菜园的专家 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 君的最大收益，以一个整数形式输出在一行中。

### 样例 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 完成