题目描述

为了庆功，学校举办了一场抽奖活动。有 $n$ 种奖品可以兑换，第 $i$ 种奖品的价格为 $p_i$ 元，价值（满意度）为 $w_i$，库存量为 $s_i$ 件。

你有预算 $m$ 元，求能获得的最大满意度。

输入格式

第一行两个整数 $n, m$。

接下来 $n$ 行，每行三个整数 $p_i, w_i, s_i$，表示奖品的价格、价值和库存。

输出格式

输出一个整数，表示最大满意度。

输入输出样例 #1

输入 #1

样例

输入

5 1000

输出

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

输出 #1

1040

说明/提示

数据范围

• $1 \le n \le 500$
• $1 \le m \le 6000$
• $1 \le p_i, w_i \le 200$
• $1 \le s_i \le 200$