题目背景

一日 pyc和xcx无聊 所以开始准备去游山玩水：） 他们本准备去到（西藏 伊斯坦布尔 耶路撒冷 纽约...）等地区 进行神秘的旅游 但在这之前 他们需要准备一个背包与许多需要使用的物品 他们以物品的体积 价值 数据去判断所需携带的物品 不过 在这种有关于数学的问题面前 他们还是大脑宕机了... 为了在出发之前快速准备好物品 他们将向你询问物品的带法 相信你一定可以用代码帮助他们哦：）

题目描述

你从pyc和xcx那里得到了一个容量为 \(V\) 的背包以及 \(n\) 种买来的物品 , 第 \(i\) 种物品的体积为 \(w_i\) , 并且每件价值为 \(val_i\) , 每个物品最多有 \(c_i\) 件

你可以选择每种物品若干件放入背包 但同一种物品选择的件数不能超过 \(c_i\) 同时总容量不能超过 \(V\)

请你求出在不超过背包容量的前提下 能获得的最大总价值

形式化题意：设第 \(i\) 种物品选择 \(x_i\) 件 则需要满足：\[\sum_{i=1}^{n} x_i \cdot w_i \le V,\quad 0 \le x_i \le c_i\]

最大化目标：\[\max \sum_{i=1}^{n} x_i \cdot val_i\]

输入格式

第一行两个整数 \(n,V\) 表示物品种类数与背包容量

接下来 \(n\) 行 每行三个整数 \(w_i,val_i,c_i\) 分别表示第 \(i\) 种物品的体积 价值与最多件数

输出格式

输出一个整数 表示最大总价值

输入输出样例 #1

输入 #1

3 10
3 4 2
4 5 3
2 3 4

输出 #1

14

说明/提示

样例解释 #1

一种可行的最优方案是：
- 选第 1 种物品 \(2\) 件->体积：\(2\times 3=6\),价值：\(2\times 4=8\)
- 选第 3 种物品 \(2\) 件->体积：\(2\times 2=4\),价值：\(2\times 3=6\)

总容量 \(6+4=10 \le 10\) 总价值 \(8+6=14\) 为最大值

数据范围

对于 \(50\%\) 的数据：\(1\le n \le 50\),\(1\le V \le 100\),\(1\le c_i \le 10\)

对于 \(100\%\) 的数据：\(1\le n \le 500\),\(1\le V \le 1000\),\(1\le c_i \le 50\)