问题 25542 --集市班车

25542: 集市班车

时间限制: 1 Sec  内存限制: 128 MB
提交: 42  解决: 23
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][368kb]

题目描述

      逛逛集市,兑兑奖品,看看节目对农夫约翰来说不算什么,可是他的奶牛们非常缺乏锻炼——如果要逛完一整天的集市,他们一定会筋疲力尽的。所以为了让奶牛们也能愉快地逛集市,约翰准备让奶牛们在集市上以车代步。
但是,约翰木有钱,他租来的班车只能在 集市上沿直线跑一次, 而且只能停靠N (1 ≤ N ≤ 20000)个地点(所有地点都以1到N之间的一个数字来表示)。现在奶牛们分成K (1 ≤ K ≤ 20000)个小组,第 i 组有Mi (1 ≤ Mi≤ N)头奶牛,他们希望从Si到Ti (1 ≤ Si<Ti≤ N)。
      由于班车容量有限,可能载不下所有想乘车的奶牛们,此时也允许小组里的一部分奶牛分开乘坐班车。约翰经过调查得知班车的容量是C (1 ≤ C ≤ 100),请你帮助约翰计划一个尽可能满足更多奶牛愿望的方案。

输入

第一行:包括三个整数:K,N和C,彼此用空格隔开。
第二行到K + 1行:在第i + 1行,将会告诉你第i组奶牛的信息:Si,Ei和Mi,彼此用空格隔开。

输出

第一行:可以坐班车的奶牛的最大头数

样例输入

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)

来源

[提交][状态]