No testdata at current.
小红在玩一款模拟经营游戏,这个游戏按时间排序有n个事件,每个事件可以在两种选项种选择一种:
(1)消耗x颗宝石,获得y枚金币。
(2)获得z颗宝石。
不过,宝石的数量是有上限的,在任何时刻,若小红的宝石数量大于m,则大于m部分的宝石直接消失。
在n个事件结束后,小红每拥有1颗宝石,都可以将其换成1枚金币。
小红初始时没有宝石,他想知道,在最优策略下,他最多可以获得多少金币
第一行输入两个整数 n,m(1≤n,m≤1000)表示事件个数和宝石上限。
接下来n行,每行输入三个整数
x,y,z(1≤x,y,z≤109),表示每一个事件。
输出一个整数表示答案。
输入
3 3
1 2 1
1 3 1
1 2 4
输出
6
第1个事件,小红选择选项2,获得1颗宝石。
第2个事件,小红选择选项1,消耗1颗宝石,获得3枚金币。
第3个事件,小红选择选项1,获得4颗宝石,但由于宝石数量上限为3,因此小红只有3颗宝石。
最后,小红将3颗宝石换成3枚金币。
因此答案为6。