3423: 糖果峡谷

吃到到前面的糖果以后，小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位整型；