问题 26095 --糖果峡谷

26095: 糖果峡谷

时间限制: 1 Sec  内存限制: 128 MB
提交: 34  解决: 15
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][39304kb]

题目描述

吃到到前面的糖果以后,小Y充满了能量,继续向前走,眼睛痴痴的望着那遥远的糖果雨。
走啊,走啊,走啊走~~~
小Y又累了,不过它的精神已经打动了糖人。
一阵风飘过,糖人又出现在小Y的面前。小Y顿时两眼放光,想从糖人那里骗到一些糖果,来堵住口水,顺便补充能量。糖人微微一笑,说道:“别妄想了,我这个世界同在,如果你打我的注意,你将永远也到不了那有糖果雨的地方!”为了更多的糖果,小Y立刻冷静下来,装出一副“我才不会打你的注意”的样子。
糖人见小Y已经平静下来。于是,一挥手,眼前景象大变。小Y揉了揉眼睛,有些不敢相信自己的眼睛,不过,这确实是真的!!
小Y现在在一个峡谷里[一线天]前,峡谷有N个糖果单位,时刻都在向下飘落着糖果,不过由于没有人来,糖果到地面就会消失,小Y一阵心痛。
糖人从手中拿出一个巨大的容器交个小Y,并告诉他,在糖果峡谷中神秘力量的推动下,他每分钟前进1个糖果单位。糖人给小Y的容器有C个格子,每个格子只可以装1个糖果。
糖果峡谷里一共有K种糖果,每种糖果有Mi个,第i种会在峡谷中离入口Si(0<Si<=N)个糖果单位出现,可以选择用容器接或不接,接住的数量是任意的,当然不能超过Mi个;如果接住以后,会在Ti分钟(Ti>0,Si+Ti<N)后真正属于小Y [接住时那一分钟也计算在内,即在走到Si+Ti-1个单位后,糖果会属于小Y],糖果属于小Y以后就不会再占用容器的空间了。
小Y此时已经被糖果冲昏了头脑,只想得到最多的糖果。所以,他向你求助,你要想办法,让小Y接住最多的糖果。

输入

第一行,三个整数K,N,C
接下来K行,每行三个数,Si,Ti,Mi

输出

输出仅一行,最大的糖果数

样例输入

4 16 3
1 3 2
2 7 3
4 4 1
9 6 2

样例输出

6

提示

【样例说明】

在进入峡谷一分钟时,接住2颗糖果,在3分钟时被吸收;在第2分钟时,借助1颗糖果,在第8分钟时被吸收;在第四分钟时,接住2颗糖果,第七分钟时被吸收;在第9分钟时,接住2颗糖果,第14分钟时被吸收;

【数据范围】

10% 0<K<=100, 0<N<=100, 0<C<=100

20% K<=2000, N<=2000, C<=2000

30% K<=5000, N<=5000, C<=5000

50% K<=50000, N<=50000, C<=30000

75% K<=500000, N<=500000, C<=50000

90% K<=1010000 N<=1010000, C<=210000

100% K<=2000000 N<=2000000, C<=210000

对于第19、20组数据,时限为2s;其余测试点为1s;

保证结果不会超过32位整型;

来源

[提交][状态]