A94852.Knapsack 2

有 $N$ 个物品，编号为 $1, 2, \ldots, N$。对于每个 $i$ ($1 \leq i \leq N$)，物品 $i$ 的重量是 $w_i$，价值是 $v_i$。

太郎君决定从这 $N$ 个物品中挑选一些放入背包带回家。背包的容量为 $W$，这意味着所选物品的总重量不能超过 $W$。

请计算太郎君能带回的物品的最大总价值。

第一行包含两个整数 $N$ 和 $W$，分别表示物品的数量和背包的容量。

接下来 $N$ 行，每行包含两个整数 $w_i$ 和 $v_i$，表示第 $i$ 个物品的重量和价值。

输出一个整数，表示太郎君能带回的物品的最大总价值。

数据范围

• 所有输入均为整数。
• $1 \leq N \leq 100$
• $1 \leq W \leq 10^9$
• $1 \leq w_i \leq W$
• $1 \leq v_i \leq 10^3$

样例解释 1

可以选择物品 $1$ 和 $3$。此时总重量为 $3 + 5 = 8$，总价值为 $30 + 60 = 90$。

样例解释 3

可以选择物品 $2, 4, 5$。此时总重量为 $5 + 6 + 3 = 14$，总价值为 $6 + 6 + 5 = 17$。