该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P1607 [USACO09FEB] Fair Shuttle G

题意

公交车一共经过 $N(1 \leq N\leq 20000)$ 个站点，从站点 $1$ 一直驶到 站点$N$。

现有 $K(1\leq K\leq 50000)$ 组奶牛，第i 组有 $M_i(1\leq M_i\leq N)$ 头奶牛，他们希望从 $S_i$ 跑到 $E_i(1\leq S_i < E_i \leq N)$。

公交车最多只能同时坐 $C(1\leq C\leq 100)$头奶牛。问：公交车不走重复路线的情况下，最多满足多少头奶牛的乘车要求。 注：每一群奶牛，可以部门满足。

输入格式

第一行三个整数：$K \ N \ C$ 。

第二行到 $K+1$ 行：在第 $i+1$ 行，将会告诉你第 $i$ 组奶牛的信息：$S_i , E_i$ 和 $M_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$。