题目描述

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

太郎决定选择其中一些物品并将它们放入一个背包中带回家。背包的容量为 $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$ $\ldots$ $w_N$ $v_N$

输出

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

示例输入1

3 8
3 30
4 50
5 60

示例输出1

90

应该选择物品 $1$ 和 $3$。然后，重量的总和为 $3 + 5 = 8$，价值的总和为 $30 + 60 = 90$。

示例输入2

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

示例输出2

5000000000

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

示例输入3

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

示例输出3

17

应该选择物品 $2, 4$ 和 $5$。然后，重量的总和为 $5 + 6 + 3 = 14$，价值的总和为 $6 + 6 + 5 = 17$。