题目描述

每种奖品有价格、价值和最多购买数量。选择一些奖品，使总价格不超过预算，求总价值的最大值。

输入格式

第一行 n,m，表示奖品种类数与预算。随后 n 行，每行依次给出一种奖品的价格、价值和最多购买数量。

输出格式

输出最大总价值。

样例

5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1

1040

数据范围

1≤n≤500，1≤m≤6000，1≤价格、价值≤1000，1≤数量≤10。