有 $N$ 种物品和一件容量是 $M$ 的背包。

第 $i$ 种物品的体积是 $v_i$ ，价值是 $w_i$，有 $s_i$ 个可供使用。

求将哪些物品放入背包，可使得这些物品的总体积不超过背包容量，且价值最大。

输出最大的价值。

输入格式

第一行输入两个正整数 $N, M$ $(1 \leq N, M \leq 2000)$ 为物品数量和背包容量

接下来 $N$ 行，每行输入两个正整数 $v_i, w_i, s_i$ $(1 \leq v_i, w_i, s_i \leq 2000)$ 分别表示第 $i$ 种物品的体积,价值和数量

输出格式

输出一个非负整数，表示答案

样例 1

输入：

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

输出：

10

来源：Luogu_U592819。本站使用重新构建的测试数据。