珍宝博览会

题目描述

每年一度的皇家珍宝博览会正在举行，你作为护卫队长，被允许在博览会结束后挑选一些珍宝带走，但前提是你的手提箱只能承重 $M$。

博览会上共有 $N$ 种珍宝，每种珍宝的属性如下：

• 重量 $w_i$。
• 价值 $v_i$。
• 展台上的存量为 $s_i$ 件。

由于博览会的珍宝种类繁多且存量巨大，之前的暴力方案可能无法在限定时间内得出结果。请利用二进制拆分或其他优化方法，计算出在手提箱限重范围内能带走的最大总价值。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示珍宝种类和手提箱限重。

接下来的 $N$ 行，每行包含三个整数 $w_i, v_i, s_i$，分别表示第 $i$ 种珍宝的重量、价值和存量。

输出格式

输出一个整数，表示能够获得的最大总价值。

输入输出样例 #1

输入 #1

3 50
10 60 4
20 100 2
30 120 10

输出 #1

240

样例 1 说明

选择 4 件第 1 种珍宝（总重 40，价值 240）是一种方案。 选择 1 件第 2 种（重 20，价值 100）和 1 件第 3 种（重 30，价值 120），总重 50，价值 220。 最优为 240。

数据范围

对于 $60\%$ 的数据，$1 \le N, M, s_i \le 100$。

对于 $100\%$ 的数据，$1 \le N \le 1000$，$1 \le M \le 2000$，$1 \le w_i, v_i \le 2000$，$1 \le s_i \le 2000$。

建议

二刷