题目描述

公交车一共经过 $n$ 个站点，从站点 $1$ 一直驶到站点 $n$。$k$ 群奶牛希望搭乘这辆公交车。第 $i$ 群牛一共有 $m_i$ 只。

他们希望从 $s_i$ 到 $e_i$ 去。 公交车只能坐 $c$ 只奶牛。而且不走重复路线，请计算这辆车最多能满足多少奶牛的要求。 注意：对于每一群奶牛，可以部分满足，也可以全部满足，也可以全部不满足。

输入格式

第一行：包括三个整数：$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

样例 1 解释

班车可以把 $2$ 头奶牛从 $1$ 送到 $5$，$3$ 头奶牛从 $5$ 送到 $8$，$2$ 头奶牛从 $8$ 送到 $14$，$1$ 头奶牛从 $9$ 送到 $12$，$1$ 头奶牛从 $13$ 送到 $14$，$1$ 头奶牛从 $14$ 送到 $15$。