L. [USACO07DEC] Charm Bracelet S

Type: RemoteJudge

1000ms

128MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有 $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 \le 100$ 。