题目描述

寒冬将至，北境要塞即将迎来一年中最漫长、最严酷的封锁期。要塞总督必须在风雪彻底封死山道之前，完成最后一次冬储采购。然而，王国拨付的军费十分有限，而商会送来的军需清单却长得看不到尽头：御寒毛毯、精炼火油、备用弓弦、疗伤药剂、战马饲料……每一种物资都有各自的单价、能够提升的要塞战备价值，以及商会最多能够提供的数量。

总督深知，钱不能乱花。买得太多，军费不够；买得太少，要塞难以撑过寒冬。更麻烦的是，有些物资虽然单价低廉，却能显著提升士兵的体力与士气；有些物资价格高昂，却只能在关键时刻发挥作用。后勤官需要在这份长长的清单中反复权衡：每一种物资究竟采购多少件，才能让有限军费换来的总战备价值最大？

现在，这份采购清单和军费预算交到了你的手中。具体来说，给定 $n$ 种军需物资和总军费 $m$。对于第 $i$ 种物资，已知其单价为 $v_i$、单件战备价值为 $w_i$，并且商会最多能提供 $s_i$ 件。每种物资可以购买 $0$ 件到 $s_i$ 件之间的任意整数件。

请选择每种物资的采购数量，使得总花费不超过军费 $m$，并且获得的总战备价值最大。注意：价格与价值是两个不同的概念，要求最大化的是总价值，而不是总价格。

输入格式

第一行两个整数 $n, m$（$n < 500$，$m < 6000$），其中 $n$ 代表希望购买的物资种数，$m$ 表示可用军费金额。
接下来 $n$ 行，每行三个整数 $v, w, s$，分别表示第 $i$ 种物资的价格、价值（价格与价值是不同的概念）和能购买的最大数量（买 $0$ 件到 $s$ 件均可），其中 $v < 100$，$w < 1000$，$s < 10$。

输出格式

输出一个整数，表示此次采购能获得的最大的总价值（注意！不是总价格）。

输入输出样例

3 10
2 3 3
3 4 2
5 10 1

17