题目描述

有 $n$ 件物品，每件物品拥有重量 $w_i$ 和价值 $v_i$。现有一个最大承重为 $W$ 的背包。 你需要从中挑选若干物品放入背包，要求物品总重量不超过背包承重，使得物品总价值尽可能大，输出最大总价值。

输入格式

第一行两个整数 $n,W$。 接下来 $n$ 行，每行两个整数 $w_i,v_i$，分别代表一件物品的重量与价值。

输出格式

输出一行一个整数，表示背包能装下的最大总价值。

样例输入 1

3 10
6 3
5 2
4 2

样例输出 1

5

样例输入 2

2 5
10 5
3 3

样例输出 2

3

数据范围

$1 \le n \le 100$ $1 \le w_i,W \le 10^9$ $1 \le v_i \le 100$