1121. LXY 的凑单计划

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 可获得的最大的满足感。

样例

标准输入 复制文本
3 10
2 1 0
3 3 1
4 5 4
标准输出 复制文本
11

提示

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

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

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

来源

2018 软件学院蓝桥杯热身赛 (For 16/17)

单点时限 1 秒
内存限制 128 MB
提交 231
通过 67