A22609.Fair Shuttle G
提高+/省选-
USACO
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
逛逛集市,兑兑奖品,看看节目对农夫约翰来说不算什么,可是他的奶牛们非常缺乏锻炼——如果要逛完一整天的集市,他们一定会筋疲力尽的。所以为了让奶牛们也能愉快地逛集市,约翰准备让奶牛们在集市上以车代步。但是,约翰木有钱,他租来的班车只能在集市上沿直线跑一次,而且只能停靠 N(1≤N≤20000) 个地点(所有地点都以 1 到 N 之间的一个数字来表示)。现在奶牛们分成 K(1≤K≤50000) 个小组,第i 组有 Mi(1≤Mi≤N) 头奶牛,他们希望从 Si 跑到 Ei(1≤Si<Ei≤N)。
由于班车容量有限,可能载不下所有想乘车的奶牛们,此时也允许小组里的一部分奶牛分开乘坐班车。约翰经过调查得知班车的容量是 C(1≤C≤100),请你帮助约翰计划一个尽可能满足更多奶牛愿望的方案。
输入格式
第一行:包括三个整数:K,N 和 C,彼此用空格隔开。
第二行到 K+1 行:在第 i+1 行,将会告诉你第 i 组奶牛的信息:Si,Ei 和 Mi,彼此用空格隔开。
输出格式
第一行:可以坐班车的奶牛的最大头数
输入输出样例
输入#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
输出#1
10
说明/提示
【样例说明】
班车可以把 2 头奶牛从 1 送到 5,3 头奶牛从 5 送到 8,2 头奶牛从 8 送到 14,1 头奶牛从 9 送到 12,1 头奶牛从 13 送到 14,1 头奶牛从 14 送到 15。