Dota是现下流行的一款著名游戏。Moe-ing和PSyaomo123也深深地爱上了这个游戏。 Dota在刚开始时，英雄拥有一定的钱，这些钱是非常重要的！它会决定你开始的补刀和被对方压制的程度，所以，你要合理的选择出门装。有些出门装你能买无限多（比如大药膏，吃树），有的呢，你只能买一样，原因有很多，所以不解释了。啊，护腕什么的，最讨厌了，但是，邪恶的我还是加上了，因为这样可以稍稍增加一点难度。（因为它可以买mi次） 现在已知一个物品有一下的几点性质：1、能买的次数mi（-1表示可以买无限次） 2、物品的价格gi 3、物品的性价比pi 当然，你出门时有一定的钱g，你要用这有限的钱买出（无限多种可能？错！）性价比之和最高的一些物品或一个物品，否则，你会拖团队的后腿！要是你真的拖了团队了后腿，你就等着被口水淹没吧~！（虽然在网上你只不过被骂……%￥……#！&*……@（￥@*）

第一行:两个正整数n，g，含义如描述 第二行到第n+1行：每行3个正整数mi，gi，pi，中间以一个空格隔开

一个正整数，表示最高能到的性价比之和。

5 603
2 150 80
1 185 50
-1 100 30
-1 90 90
1 170 100

540

Moe-ing 与 Psyaomo123联合出题