题目描述

给定 $N$ 种物品和一个容量为 $W$ 的背包，第 $i$ 种物品的重量为 $w_i$，价值为 $v_i$，最多可以取 $s_i$ 件。

请问：在不超过背包容量的前提下，最多能凑出多大价值的物品总和？

输入格式

N W
w_1 v_1 s_1
w_2 v_2 s_2
…
w_N v_N s_N

• 第一行包含两个整数 $N,W$，分别表示物品种类数和背包容量。
• 接下来 $N$ 行，每行三个整数 $w_i,v_i,s_i$，分别表示第 $i$ 类物品的重量、价值和可取件数。

输出格式

ans

• 仅一行，输出能取得的最大总价值。

3 10
3 4 2
4 5 1
2 3 3

14

解释：

• 可取 2 件第 1 类（重量 $3×2=6$，价值 $4×2=8$）
• 可取 2 件第 3 类（重量 $2×2=4$，价值 $3×2=6$）
• 总重量 $6+4=10$，总价值 $8+6=14$ —— 超出容量，调整为：
• 取 2 件第 1 类（重量 6，价值 8）+ 1 件第 2 类（重量 4，价值 5）→ 总重量 10 ，总价值 13
• 或者取 1 件第 1 类+1 件第 2 类+3 件第 3 类 → 重量 3+4+6=13 超出…
• 最优方案是取 2 件第 1 类 + 1 件第 3 类：重量 6+2=8 ，价值 8+3=11；或者取 1 件第 2 类 + 3 件第 3 类：重量 4+6=10 ，价值 5+9=14；
• 其中取 1 件第 2 类 + 3 件第 3 类 的价值 14 为最优。

（此处样例结果应为 14）

2 10
3 5 3
5 10 2

20

数据范围

• $1 \le N \le 1000$
• $1 \le W \le 10000$
• $1 \le w_i,v_i,s_i \le 1000$

要求算法在 $O\bigl(N\log s_{\max}\times W\bigr)$ 或 $O(NW)$（二进制拆分后）内完成。