#BPV03. 临时通行证
临时通行证
临时通行证
探险队出发前,可以在补给站购买几种临时通行证。第 i 种通行证每张花费 c_i 枚代币,使用后能帮助队伍前进 d_i 千米,补给站只剩 s_i 张。
一张通行证只能使用一次,同种通行证可以买多张。不同通行证提供的前进距离直接相加,没有其他限制。
队伍最多花费 B 枚代币,可以不花完。求能够获得的最大总前进距离。
输入格式
第一行两个整数 N、B。
接下来 N 行,每行三个整数 c_i、d_i、s_i。
输出格式
输出一个整数,表示题目所求的最大值。
数据范围
1 ≤ N ≤ 30,1 ≤ B ≤ 100;1 ≤ c_i ≤ 100,1 ≤ d_i ≤ 10000,1 ≤ s_i ≤ 100。
样例
输入
3 10
3 5 2
4 7 1
2 3 3
输出
17
说明
购买第 1 种两张、第 2 种一张,共花费 10 枚代币,可前进 17 千米。