A2896. 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)$，请你帮助约翰计划一个尽可能满足更多奶牛愿望的方案。
由于班车容量有限，可能载不下所有想乘车的奶牛们，此时也允许小组里的一部分奶牛分开乘坐班车。约翰经过调查得知班车的容量是 $C(1\leq C\leq 100)$，请你帮助约翰计划一个尽可能满足更多奶牛愿望的方案。
输入格式
第一行：包括三个整数：$K,N$ 和 $C$，彼此用空格隔开。
第二行到 $K+1$ 行：在第 $i+1$ 行，将会告诉你第 $i$ 组奶牛的信息：$S_i,E_i$ 和 $M_i$，彼此用空格隔开。
第二行到 $K+1$ 行：在第 $i+1$ 行，将会告诉你第 $i$ 组奶牛的信息：$S_i,E_i$ 和 $M_i$，彼此用空格隔开。
输出格式
第一行：可以坐班车的奶牛的最大头数
输入输出样例
输入 #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$。
班车可以把 $2$ 头奶牛从 $1$ 送到 $5$，$3$ 头奶牛从 $5$ 送到 $8$，$2$ 头奶牛从 $8$ 送到 $14$，$1$ 头奶牛从 $9$ 送到 $12$，$1$ 头奶牛从 $13$ 送到 $14$，$1$ 头奶牛从 $14$ 送到 $15$。