题目描述

琦琦立志当军，而战术背包能提高一个士兵的战力。 一共有 $\red{n（1<=n<=100）}$个物品供琦琦选择，每个物品有三个属性，$\red{a_i}$ 表示大小，$\red{b_i}$ 表示战力值，$\red{c_i}$ 表示为该物品的数量 而琦琦的背包容量为$\red{ L (1<=L<=100000)}$，他想知道他能携带的最大战力是多少？

输入格式

第一行，两个整数，$\red{n，L}$。 第二到$\red{n+1}$行，每行三个整数，$\red{a_i}$，$\red{b_i}$，$\red{c_i}$。

输出格式

共一行，第一行一个整数，表示最大战力

样例

输入样例

3 10
2 2 3
7 10 2
3 4 2

输出样例

14

提示

对于$\red{100\%}$的数据：

$\red{1<=a_i<=100000}$ $\red{1<=b_i<=100}$ $\red{1<=c_i<=100}$