P12196 [NOISG 2025 Prelim] Lasers 2

Pavement 从 Gohcart 那里购买了一个激光玩具（Gohcart 原先是从 Rar the Cat 那里买的）。这个玩具有一个由 $h$ 行 $w$ 列组成的网格。网格的行编号从上到下为 $1$ 到 $h$，列编号从左到右为 $1$ 到 $w$。 每一行恰好包含一个上锁的滑动墙。初始时，第 $i$ 行的墙覆盖第 $l[i]$ 列到第 $r[i]$ 列（从 $1$ 开始编号），解锁它需要花费 $c[i]$ 美元。墙一旦解锁，就可以在第 $i$ 行上水平滑动到任意位置，只要它对齐在网格的边缘内即可。墙的任何部分都不能超出玩具的左边缘或右边缘。 每一列的顶部都有一个朝下的激光。如果某个滑动墙位于第 $i$ 列，那么它将阻挡第 $i$ 列上的激光。 一个可能的玩具示例如下，其中 $h = 3$，$w = 10$：  给定总预算 $k$ 美元，Pavement 的目标是在合理解锁并滑动墙壁的情况下，最大化未被阻挡的激光数量。请你确定他最多可以实现多少束未被阻挡的激光。

无

无

### 子任务 对于所有测试用例，输入将满足以下约束条件： - $1 \leq h, w \leq 2000$ - $0 \leq k \leq 10^9$ - 对所有 $1 \leq i \leq h$，满足 $1 \leq l[i] \leq r[i] \leq w$ - 对所有 $1 \leq i \leq h$，满足 $0 \leq c[i] \leq 10^9$ 你的程序将在满足以下特殊性质的输入数据上进行测试： | 子任务 | 分数 | 特殊性质 | | :-: | :-: | :-: | | $0$ | $0$ | 样例 | | $1$ | $6$ | $k = 0, c[i] = 10^9$ | | $2$ | $9$ | $l[i] = r[i]$ | | $3$ | $10$ | $h, w \leq 18$ | | $4$ | $7$ | $h, w \leq 100, k \leq 2000$ | | $5$ | $15$ | $h, w \leq 100$ | | $6$ | $23$ | $h, w \leq 500$ | | $7$ | $8$ | $r[1] − l[1] = r[2] − l[2] = \ldots = r[h] − l[h]$ | | $8$ | $22$ | 无 | ### 样例 1 解释 上图的激光玩具正对应该测试用例。Pavement 可以以 $9 + 1 = 10$ 美元的总价解锁第一个和第二个滑动墙。然后他可以将第一个滑动墙滑动到覆盖第 $4$ 到 $7$ 列，将第二个滑动墙滑动到覆盖第 $5$ 到 $7$ 列。  这样一来，$6$ 束激光（第 $1, 2, 3, 8, 9, 10$ 列）未被阻挡，这是能够实现的最大数量。 此样例适用于子任务 $3, 4, 5, 6, 8$。 ### 样例 2 解释 此样例适用于子任务 $2$ 到 $8$。 ### 样例 3 解释 此样例适用于子任务 $1, 3, 4, 5, 6, 8$。