[Usaco2009 Feb]庙会捷运Fair Shuttle

公交车经过 $N$ 个站点，编号从 $1$ 到 $N$。共有 $K$ 群奶牛希望搭乘这辆公交车，第 $i$ 群奶牛有 $M_i$ 只，想要从站点 $S_i$ 前往站点 $E_i$。

公交车在行驶过程中最多可同时搭载 $C$ 只奶牛，并且只能沿站点编号递增的方向行驶。请计算这辆公交车最多能够满足多少只奶牛的乘车要求。

对于每一群奶牛，可以只满足其中一部分，也可以全部满足或全部不满足。

输入格式

第 $1$ 行包含三个整数 $K$、$N$ 和 $C$，用空格隔开。

第 $2$ 至第 $K+1$ 行，每行包含三个整数 $S_i$、$E_i$ 和 $M_i$，表示第 $i$ 群奶牛的信息，用空格隔开。

输出格式

输出一行，表示最多能够搭乘公交车的奶牛总数。

样例输入

8 15 3
1 5 2
13 14 1
5 8 3
8 14 2
14 15 1
9 12 1
12 15 2
4 6 1

样例输出

10

样例解释

公交车可以将 $2$ 只奶牛从展台 $1$ 送到展台 $5$，将 $3$ 只奶牛从展台 $5$ 送到展台 $8$，将 $2$ 只奶牛从展台 $8$ 送到展台 $14$，将 $1$ 只奶牛从展台 $9$ 送到展台 $12$，将 $1$ 只奶牛从展台 $13$ 送到展台 $14$，并将 $1$ 只奶牛从展台 $14$ 送到展台 $15$，共计满足 $10$ 只奶牛的乘车要求。

数据范围

• $1\le N\le 20000$；
• $1\le K\le 50000$；
• $1\le C\le 100$；
• $1\le M_i\le N$。

来源与许可

本题为 USACO 2009 年 2 月赛题目「Fair Shuttle」，题面与测试数据整理自 BZOJ 1577。

样例 1

输入

8 15 3
1 5 2
13 14 1
5 8 3
8 14 2
14 15 1
9 12 1
12 15 2
4 6 1

输出

10