07463. Knapsack 2 未做

有 $N$ 个物品，编号为 $1,2,\dots ,N$。第 $i$ 个物品的重量为 $w_i$，价值为 $v_i$。

太郎要从 $N$ 个物品中选出若干放入背包带回家。背包的容量为 $W$，也就是说，带回家的物品重量总和不能超过 $W$。

求太郎能带回家的物品价值总和的最大值。

输入按以下格式从标准输入给出：

N W
w_1 v_1
w_2 v_2
⋮
w_N v_N

输出太郎能带回家的物品价值总和的最大值。

数据范围

• $1\le N\le 100$
• $1\le W\le 10^9$
• $1\le w_i\le W$
• $1\le v_i\le 10^3$

样例说明 1

选中第 1、3 个物品：重量 $3+5=8\le 8$，价值 $30+60=90$ —— 最优。

提示：容量 $W$ 高达 $10^9$，开不下「容量做下标」的数组——把下标换成「价值」。

来源：AtCoder Educational DP Contest（dp_e）。本页为题面搬运；本站数据为按题目要求自造的完整数据包，也推荐去原网站提交对比。