Cleaning Shifts 清理牛棚

题目描述:

约翰的奶牛们从小娇生惯养，她们无法容忍牛棚里的任何脏东西．约翰发现，如果要使这群有洁癖的奶牛满意，他不得不雇佣她们中的一些来清扫牛棚, 约翰的奶牛中有N(1≤N≤10000)头愿意通过清扫牛棚来挣一些零花钱．由于在某个时段中奶牛们会在牛棚里随时随地地乱扔垃圾，自然地，她们要求在这段时间里，无论什么时候至少要有一头奶牛正在打扫．需要打扫的时段从某一天的第M秒开始，到第E秒结束f0≤M≤E≤86399)．注意这里的秒是指时间段而不是时间点，也就是说，每天需要打扫的总时间是E-M+I秒． 约翰已经从每头牛那里得到了她们愿意接受的工作计划：对于某一头牛，她每天都愿意在笫Ti，.T2秒的时间段内工作(M≤Ti≤马≤E)，所要求的报酬是S美元(0≤S≤500000)．与需打扫时段的描述一样，如果一头奶牛愿意工作的时段是每天的第10_20秒，那她总共工作的时间是11秒，而不是10秒．约翰一旦决定雇佣某一头奶牛，就必须付给她全额的工资，而不能只让她工作一段时间，然后再按这段时间在她愿意工作的总时间中所占的百分比来决定她的工资．现在请你帮约翰决定该雇佣哪些奶牛以保持牛棚的清洁，当然，在能让奶牛们满意的前提下，约翰希望使总花费尽量小．

输入格式:

输出格式:

样例输入:

3 0 4 //三头牛,要打扫从0到4号stall
0 2 3 //一号牛,从0号stall打扫到2号,工资为3
3 4 2
0 0 1

样例输出:

5

提示:

约翰有3头牛，牛棚在第0秒到第4秒之间需要打扫．第1头牛想要在第0，1，2秒内工作，为此她要求的报酬是3美元．其余的依此类推．    约翰雇佣前两头牛清扫牛棚，可以只花5美元就完成一整天的清扫．

时间限制: 1000ms
空间限制: 256MB

---

来源: Usaco2005 Dec