题目描述

小明有 $m$ 元钱，书店有 $n$ 种书。第 $i$ 种书的价格为 $p_i$ 元，页数为 $a_i$ 页，库存量为 $c_i$ 本。

小明想用这些钱买书，使得买到的书的总页数最多。每种书最多买 $c_i$ 本。

输入格式

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

接下来 $n$ 行，每行三个整数 $p_i, a_i, c_i$。

输出格式

输出一个整数，表示最多能买到的总页数。

输入输出样例 #1

输入 #1

样例

输入

3 20

输出

3 100 3
5 200 2
8 300 1

输出 #1

700

说明/提示

样例解释：买3本第1种书（9元，300页）和1本第3种书（8元，300页），共17元，600页？

让我重新计算：

• 第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$