题目描述

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

$\red{1<=a_i<=100000}$

$\red{1<=b_i<=100}$

$\red{1<=c_i<=100}$

输入格式

第一行，两个整数，$\red{n，}$$\red{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