[Usaco2009 Feb]庙会捷运Fair Shuttle
时间限制：10s 空间限制：64MB
题目描述
公交车一共经过N（1<=N<=20000）个站点，从站点1一直驶到站点N。K（1<=K<=50000)群奶牛希望搭乘这辆公交车。第i群牛一共有Mi（1<=Mi<=N)只.
他们希望从Si到Ei去。
公交车只能座C（1<=C<=100）只奶牛。而且不走重复路线，请计算这辆车最多能满足多少奶牛听要求。
注意：对于每一群奶牛，可以部分满足，也可以全部满足，也可以全部不满足。
输入格式
第1行： 三个整数： K，N，C。 由空格隔开。
第2..K+1行：第i+1行，告诉你第i组奶牛的信息： S_i, E_i and 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
提示
捷运可以把2头奶牛从展台1送到展台5，3头奶牛从展台5到展台8， 2头奶牛从展台8 到展台14，1头奶牛从展台9送到展台12，一头奶牛从展台13送到展台14， 一头奶牛从 14送到15。
题目来源
Gold