07453. Charm Bracelet S 未做

有 $N$ 件物品和一个容量为 $M$ 的背包。第 $i$ 件物品的重量是 $W_i$，价值是 $D_i$。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

第一行：物品个数 $N$ 和背包大小 $M$。

第二行至第 $N+1$ 行：第 $i$ 个物品的重量 $W_i$ 和价值 $D_i$。

输出一行最大价值。

$1\le N\le 3402$，$1\le M\le 12880$，$1\le W_i\le 400$，$1\le D_i\le 100$。

来源：洛谷 P2871（Charm Bracelet S）。本页为题面搬运；本站数据为按题目要求自造的完整数据包，也推荐去原网站提交对比。