题目描述

$N$ 个物品被编号为 $1, 2, \ldots, N$。对于 $1 \leq i \leq N$，物品 $i$ 的重量是 $w _ i$，价值是 $v _ i$。

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

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

输入格式

第一行输入 $N,W$。

接下来 $N$ 行，每行输入两个整数 $w_i,v_i$。

输出格式

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

3 8
3 30
4 50
5 60

90

1 1000000000
1000000000 10

10

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

17

提示

样例 1 解释

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

样例 3 解释

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

数据范围

• 所有输入均为整数。
• $1 \leq N \leq 100$
• $1 \leq W \leq 10 ^ 9$
• $1 \leq w _ i \leq W$
• $1 \leq v _ i \leq 10 ^ 3$