OI题库

【题目描述】

约翰的奶牛们从小娇生惯养。她们无法容忍牛棚里的任何脏东西。约翰发现，如果要使这群有洁癖的奶牛满意，它不得不雇佣她们中的一些来清扫牛棚。

约翰的奶牛中有N(1<=N<=10000)头愿意通过清扫牛棚来挣一些零花钱。由于在某个时段中奶牛们会在牛棚里随时随地地乱扔垃圾，自然地，她们要求在这段时间里，无论什么时候至少要有一头奶牛正在打扫。需要打扫的时段从某一天的第M秒开始，到第E秒结束（0<=M<=E<=86399）.注意这里的秒是指时间段而不是时间点。也就是说，每天需要打扫的总时间是E-M+1秒。

约翰已经从每头牛哪里得到了她们愿意接受的工作计划：对于每一头牛，她每天都愿意在第T1..T2秒的时间段内工作（M<=T1<=T2<=E），所要求的报酬是S美元（0<=S<=500000）。与需打扫时段的描述一样，如果一头奶牛愿意工作的时段是每天的第10..20秒，那她总共工作的时间是11秒，而不是10秒。约翰一旦决定雇佣某一头奶牛，就必须付给她全额的工资，而不能只让她工作一段时间，然后再按这段时间在她愿意工作的总时间中所占的百分比来决定她的工资。

现在请你帮约翰决定该雇佣那些奶牛以保持牛棚的清洁，当然，在能让奶牛们满意的前提下，约翰希望使总花费尽量小。

【输入格式】

第1行：3个正整数N,M,E，用空格隔开。

第2到N+1行：第i+1行给出了编号为i的奶牛的工作计划，即3个用空格隔开的正整数T1,T2,S.

【输出格式】

输出一个整数，表示约翰需要为牛棚清理工作支付的最少费用。如果清理工作不可能完成，那么输出-1.

【样例输入】

3 0 4
0 2 3
3 4 2
0 0 1

【样例输出】

5

【提示】

约翰有3头牛。牛棚在第0秒到第4秒之间需要打扫。第1头牛想要在0，1，2秒内工作，为此她要求的报酬是3美元，其余的依此类推。

【来源】

Coaches,2004

USACO DEC05 Silver,clean

Translate by：庄乐