← 返回题目
题库练习 Fair Shuttle G
← 上一题 下一题 →

A2896 | Fair Shuttle G

来源USACO / 2009
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

逛逛集市，兑兑奖品，看看节目对农夫约翰来说不算什么，可是他的奶牛们非常缺乏锻炼——如果要逛完一整天的集市，他们一定会筋疲力尽的。所以为了让奶牛们也能愉快地逛集市，约翰准备让奶牛们在集市上以车代步。但是，约翰木有钱，他租来的班车只能在集市上沿直线跑一次，而且只能停靠 $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)$，请你帮助约翰计划一个尽可能满足更多奶牛愿望的方案。

输入格式

第一行：包括三个整数：$K,N$ 和 $C$，彼此用空格隔开。

第二行到 $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
C++ 编辑器
输入
输出