问题陈述

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

太郎决定从 $N$ 个物品中选择一些物品装进背包里带回家。背包的容量为 $W$ ，这意味着所取物品的重量之和最多为 $W$ 。

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

限制因素

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

输入

输入内容由标准输入法提供，格式如下：

• $N$ $W$
• $w_1$ $v_1$
• $w_2$ $v_2$
• $:$
• $w_N$ $v_N$

输出

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

3 8
3 30
4 50
5 60

90

应取物品 $1$ 和 $3$ 。那么，重量之和为 $3 + 5 = 8$ ，价值之和为 $30 + 60 = 90$ 。

5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

5000000000

答案可能不适合 32 位整数类型。

6 15
6 5
5 6
6 4
6 6
3 5
7 2

17

应取物品 $2, 4$ 和 $5$ 。那么，重量之和为 $5 + 6 + 3 = 14$ ，价值之和为 $6 + 6 + 5 = 17$ 。

来源

https://atcoder.jp/contests/dp/tasks/dp_d