题目描述

小明有 $m$ 元钱，书店有 $n$ 种书。第 $i$ 种书的价格为 $p_i$ 元，页数为 $a_i$ 页，库存量为 $c_i$ 本。小明想用这些钱买书，使得买到的书的总页数最多。每种书最多买 $c_i$ 本。

输入格式

第一行包含两个整数 $n,m$，分别表示书的种类数和预算金额。

接下来 $n$ 行，每行包含三个整数 $p_i,a_i,c_i$，依次表示第 $i$ 种书的价格、页数和库存量。

输出格式

一行一个整数，表示能买到的最大总页数。

样例

3 20
3 100 3
5 200 2
8 300 1

700

样例解释

共有三种书，预算 $20$ 元：

• 第 $1$ 种：价格 $3$ 元，页数 $100$，库存 $3$ 本；
• 第 $2$ 种：价格 $5$ 元，页数 $200$，库存 $2$ 本；
• 第 $3$ 种：价格 $8$ 元，页数 $300$，库存 $1$ 本。

最优方案：购买 $2$ 本第 $2$ 种书（花费 $10$ 元，获得 $400$ 页）和 $1$ 本第 $3$ 种书（花费 $8$ 元，获得 $300$ 页），总花费 $18$ 元，总页数 $700$。没有其他方案能获得更大页数。

提示

• $1 \le n \le 100$
• $1 \le m \le 1000$
• $1 \le p_i,a_i \le 1000$
• $1 \le c_i \le 100$