问题陈述

有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^9$

$1 \leq w_i \leq W$

$1 \leq v_i \leq 10^3$

输入

输入以以下格式从标准输入中获取：

$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

1 1000000000
1000000000 10

样例输出 2

10

样例输入 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。