题目描述

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

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

输入格式

第 $1$ 行： 三个整数：$k,n,c$，由空格隔开。

第 $2\sim 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

数据规模与约定

对于 $100\%$ 的数据，$1\leq n\leq 20000$，$1\leq k\leq 50000$，$1\leq m_i\leq n$，$1\leq c\leq 100$。

提示

捷运可以把 $2$ 头奶牛从展台 $1$ 送到展台 $5$，$3$ 头奶牛从展台 $5$ 到展台 $8$，$2$ 头奶牛从展台 $8$ 到展台 $14$，$1$ 头奶牛从展台 $9$ 送到展台 $12$，一头奶牛从展台 $13$ 送到展台 $14$，一头奶牛从 $14$ 送到 $15$。

题目来源

Usaco 2009 Feb Gold