战略储备

题目描述

在一个庞大的帝国军械库中，为了应对即将到来的防御战，你需要从仓库中挑选武器进行战略储备。货车承重上限为 $M$。

军械库中共有 $N$ 种武器，每种武器的重量为 $w_i$，威力值为 $v_i$，最大供应量为 $s_i$。

由于仓库规模极巨，请确保你的算法足够高效（建议使用二进制优化的多重背包），能够在给定的时间内处理大规模数据。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示武器种类和货车承重上限。

接下来的 $N$ 行，每行包含三个整数 $w_i, v_i, s_i$。

输出格式

输出一个整数，表示在承重范围内能获得的最大总威力值。

输入输出样例 #1

输入 #1

5 1000
10 50 100
20 120 50
50 300 10
100 700 5
1 1 1000

输出 #1

7100

数据范围

对于 $100\%$ 的数据，$1 \le N \le 1000$，$1 \le M \le 10^5$，$1 \le w_{i} \le M$，$1 \le v_{i} \le 10^9$，$1 \le s_{i} \le 10^5$。 注意：总价值可能超过 int 范围，请使用 long long。

建议

三刷