题目描述

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 的目标是在合理解锁并滑动墙壁的情况下，最大化未被阻挡的激光数量。请你确定他最多可以实现多少束未被阻挡的激光。

输入格式

第一行输入包含三个用空格分隔的整数 $h, w$ 和 $k$，分别表示网格的行数、列数和预算。

接下来的 $h$ 行中，每行包含三个用空格分隔的整数，表示第 $i$ 行的滑动墙的信息，分别是 $l[i]$、$r[i]$ 和 $c[i]$。

输出格式

输出一个整数，表示最多可以实现的未被阻挡的激光数量。

样例输入 1

3 10 10
2 5 9
1 3 1
4 7 10

样例输出 1

6

样例输入 2

10 10 50
8 8 0
3 3 0
6 6 2
7 7 9
1 1 50
5 5 21
6 6 4
10 10 4
10 10 3
10 10 3

样例输出 2

9

样例输入 3

4 17 0
2 4 1000000000
6 9 1000000000
8 13 1000000000
15 16 1000000000

样例输出 3

4

说明

样例解释

对于样例 $1$，上图的激光玩具正对应该测试用例。Pavement 可以以 $9 + 1 = 10$ 美元的总价解锁第一个和第二个滑动墙。然后他可以将第一个滑动墙滑动到覆盖第 $4$ 到 $7$ 列，将第二个滑动墙滑动到覆盖第 $5$ 到 $7$ 列。

这样一来，$6$ 束激光（第 $1, 2, 3, 8, 9, 10$ 列）未被阻挡，这是能够实现的最大数量。此样例适用于子任务 $3, 4, 5, 6, 8$。

样例 $2$ 适用于子任务 $2 \sim 8$。

样例 $3$ 适用于子任务 $1, 3, 4, 5, 6, 8$。

其它样例说明

• 样例 $4 \sim 11$：见选手目录下的 lasers/lasers4.in ~ 11.in 与相应的 .ans，这些样例分别满足子任务 $1 \sim 8$ 的约束条件。

数据范围

对于所有测试用例，满足以下约束条件：

• $1 \le h, w \le 2000$
• $0 \le k \le 10^9$
• 对于所有 $1 \le i \le h$，满足 $1 \le l[i] \le r[i] \le w$
• 对于所有 $1 \le i \le h$，满足 $0 \le c[i] \le 10^9$

各子任务的附加限制如下表所示：