### 问题描述 新一是一位资深的侦探，为了庆祝自己最近破解的一起重大案件，他决定举办一场小型庆祝会，需要购买一些奖品奖励那些在调查过程中给予他很大帮助的人。他有一份奖品清单，上面列出了他想要购买的奖品的种类、每种奖品的价格、价值和他愿意购买的最大数量。 然而，新一作为一个理性的消费者，他想要在有限的预算下，购买总价值最高的奖品。请你帮助新一计划他的购物清单。 有 $n$ 种奖品，预算为 $m$ ，每种奖品有一个价格 $v$，一个价值 $w$，和新一愿意购买的最大数量 $s$。 请计算新一最多可以购买的奖品的总价值。 ### 输入格式 输入的第一行包含两个整数 $n$ 和 $m$，分别表示奖品的种类数和新一的预算。 接下来的 $n$ 行，每行包含三个整数 $v$、$w$、$s$，表示每种奖品的价格、价值和新一愿意购买的最大数量。 数据范围保证：$n≤500$，$m≤6000$，$v≤100$，$w≤1000$，$s≤10$。 ### 输出格式 输出一行，表示新一最多可以购买的奖品的总价值。 ### 样例输入 ```text 5 1000 80 20 4 40 50 9 30 50 7 40 30 6 20 20 1 ``` ### 样例输出 ```text 1040 ```