#27. 0/1 背包

題目描述

有 $N$ 個物品和一個容量為 $W$ 的背包。第 $i$ 個物品重量為 $w_i$、價值為 $v_i$。每個物品只能拿一次（拿或不拿），總重量不能超過 $W$。

求能帶走的最大總價值。

輸入格式

第一行兩個整數 $N, W$（$1 \le N \le 100$，$1 \le W \le 10^4$）。 接下來 $N$ 行，每行兩個整數 $w_i, v_i$（$1 \le w_i \le 10^4$，$1 \le v_i \le 10^9$）。

輸出格式

一行一個整數：最大總價值。

提示：總價值可能超過 32 位元整數範圍。