题目描述

背包体积为V，给出N个物品，每个物品占用体积为Vi，价值为Wi，每个物品要么至多取1件，要么至多取mi件（mi > 1），要么数量无限，在所装物品总体积不超过V的前提下所装物品的价值的和的最大值是多少？

输入格式

第一行两个数N、V；
下面N行每行三个数Vi、Wi、Mi表示每个物品的体积、价值与数量，Mi=1表示至多取一件，Mi>1表示至多取Mi件，Mi=-1表示数量无限。

输出格式

1个数Ans表示所装物品价值的最大值。

样例数据

input

2 10
3 7 2
2 4 -1

output

22

数据范围及提示

对于100%的数据,V <= 200000 , N <= 200