宝岛

题目描述

作为船长的你，现在来到了一个宝岛，宝岛上有银锭、珍珠、金戒指、古玩、字画、钻石等一系列奇珍异宝。每种宝贝有三个属性，分别是重量 $w$、价值 $v$、数量 $s$；遗憾的是，你的船舱载重量有限，所以只能带走一部分宝贝，不然，就会沉船了！

那么，把哪些宝贝搬进船舱，可以使得总价值最大、并且不超载呢？

输入格式

第一行含 $N$ 种宝物与船舱最大载重 $M$，用空格隔开（$1 \le N \le 10^2$，$1 \le M \le 10^5$）。

接下来 $N$ 行，每行三个整数 $w、v、s$，分别表示第 $i$ 种宝物的重量、价值、数量（$1 \le w, c, s \le 10^3$）。

输出格式

一个整数，表示在不超载的情况下，可以获得的最高总价值。

样例输入 #1

3 13
2 4 8
3 7 2
4 10 1

样例输出 #1

29

样例解释

理论上，选 3 个 3 号物品可以达到最大价值 30；

但是很可惜，3 号物品只有 1 个；故采取如下方案：

1 号物品 (2,4) 选 3 个，重量为 6，价值为 12

2 号物品 (3,7) 选 1 个，重量为 3，价值为 7

3 号物品 (4,10) 选 1 个，重量为 4，价值为 10

总价值为 29 达到最大，总重量为 13 刚好不超载。

数据范围

对于 $100\%$ 的数据：$1 \le N \le 10^2$，$1 \le M \le 10^5$，$1 \le w, c, s \le 10^3$。

知识点与难度

本题涉及的知识点从属于 GESP七级（复杂DP：多重背包、二进制拆分优化），难度等级：Mid。

测试点分布