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

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

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

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

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

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

题目

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

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

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

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

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

样例输入 2

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

样例输出 2

1000

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

样例 1 解释

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

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

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

数据范围

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

• （）
• （）
• （）

子任务

子任务 1 [10 分]

子任务 2 [10 分]

子任务 3 [10 分]

子任务 4 [50 分]

• （）

子任务 5 [20 分]

• 无额外限制

翻译由 Qwen3-235B 完成