j02057. 零食补给站 未做

补给站里有 $n$ 种零食，第 $i$ 种每包重 $w_i$、美味值 $v_i$，货源充足，每种可以买任意多包（也可以一包不买）。你有一个承重上限为 $W$ 的背囊，在总重量不超过 $W$ 的前提下，求买下零食美味值总和的最大值。

第一行两个整数 $n$ 和 $W$，表示零食种数与背囊承重上限。接下来 $n$ 行，每行两个整数 $w_i$ 和 $v_i$，表示第 $i$ 种零食的单包重量与美味值。

一行一个整数，表示能获得的最大美味值总和。

• 对于 30% 的数据：$n$ $\le$ 8，$W$ $\le$ 150，$v_i$ $\le$ 30（可爆搜每种买几包）。
• 对于 60% 的数据：$n$ $\le$ 100，$W$ $\le$ 3000，$v_i$ $\le$ $10^4$。
• 对于 100% 的数据：$n$ $\le$ 1000，$W$ $\le$ $10^4$，1 $\le$ $w_i$ $\le$ $W$，1 $\le$ $v_i$ $\le$ $10^4$，$1\le i\le n$。