LXY 由于某次比赛未能出席，让 HYR 和 CGY 去死亡 2V3，躺在床上拿了一次银奖的关系，要请 HYR 和 CGY 吃饭。如今一行人来到了北京，人生地不熟选了一家酒店吃饭。正所谓见者有份，LXY 准备通过本次买单以还清 HYR 和 CGY 的恩情，但是 Dr.Su 却决定如果本次订单金额大于 S，就由他来代出。LXY 是个吃货，他想尽量的多吃东西，而且不让苏博士来买单，于是他决定把钱用在刀刃上。

已知每道菜的价格为 P_i，满足感为 W_i，一道菜最多可以点 X_i 次（X_i=0 表示可以点无限次）。LXY 希望点单的价格不超过 S 的同时使得满足感最大。

LXY 虽然这样想，但是无奈数学太差，于是他找到了你，希望你帮他写一个程序算一下他最多能有多满足。

第一行输入 N,S \ (1 \leq N \leq 30,1 \leq S \leq 500) 分别表示有多少种食物和 Dr.Su 将会买单的价格。

接下来 N 行，每行输入三个正整数 P_i,W_i,X_i \ (1 \leq P_i≤500,0≤W_i≤300,0≤X_i≤S)，分别表示第 i 道食物的价格，满足感和可以点的次数（0 表示可以点无限次）。

输出 LXY 可获得的最大的满足感。

第一种食物点 1 份，第三种食物点 2 份。

总价格为 1 \times 2+4 \times 2=10。

最大满足感为 1 \times 1+5 \times 2=11。