[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