题目描述

模板题目。

由$n$个物品和一个容量为$v$的背包，背包可以承受的最大重量是$m$。

每个物品只可以用一次（这里可以升级成为多次，就可以和多种背包问题进行结合）。体积是$v_i$，重量是$m_i$，价值是$w_i$。

请问在重量不超过$m$，并且选择的物品的总体积不超过$v$的最大价值是多少。

样例输入

第一行三个整数$n, v, m$。

接下来$n$行，每行三个整数$v_i, m_i, w_i$。

样例输出

输出一个整数作为答案。

样例

样例一

4 5 6
1 2 3
2 4 4
3 4 5
4 5 6

8

数据范围

$1 \le n \le 10^{3}$

$1 \le v,m \le 100$

$1 \le v_i, m_i \le 100$

$1 \le w_i \le 1000$