该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背包

题目描述

$N$ 个物品被编号为 $1, 2, \ldots, N$。对于 $1 \le i \le N$，物品 $i$ 的重量是 $w_i$，价值是 $v_i$。

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

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

输入格式

第一行两个整数 $N, W$。

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

输出格式

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

数据范围与约定

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

样例输入 1

3 8
3 30
4 50
5 60

样例输出 1

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