bzoj#P1577. [Usaco2009 Feb]庙会捷运Fair Shuttle

[Usaco2009 Feb]庙会捷运Fair Shuttle

题目描述

公交车一共经过 nn 个站点,从站点 11 一直驶到站点 nnkk 群奶牛希望搭乘这辆公交车。第 ii 群牛一共有 mim_i 只。

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

输入格式

11 行: 三个整数:k,n,ck,n,c,由空格隔开。

2k+12\sim k+1 行:第 i+1i+1 行给出第 ii 组奶牛的信息:si,ei,mis_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%100\% 的数据,1n200001\leq n\leq 200001k500001\leq k\leq 500001min1\leq m_i\leq n1c1001\leq c\leq 100

提示

捷运可以把 22 头奶牛从展台 11 送到展台 5533 头奶牛从展台 55 到展台 8822 头奶牛从展台 88 到展台 141411 头奶牛从展台 99 送到展台 1212,一头奶牛从展台 1313 送到展台 1414,一头奶牛从 1414 送到 1515

题目来源

Usaco 2009 Feb Gold