题目描述

有 $N$ 个物品，从 $1$ 到 $N$ 编号。物品 $i$ 的重量是 $w_i$ 克，价值是 $v_i$ 元。

有一个容量（即承重量）是 $M$ 克的背包。

今要从 $N$ 个物品中选一些放进背包，所选物品的重量之和不能超过背包的容量。

求所选物品的总价值可能达到的最大值。 数据范围

$1 \le N \le 100$

$1 \le M \le 10^5$

$1 \le w_i \le M$

$1 \le v_i \le 10^9$

$M, w_i, v_i$ 都是整数。

输入格式

$N$ $M$

$w_1$ $v_1$

$w_2$ $v_2$

$\vdots$

$w_N$ $v_N$

输出格式

输出答案。

3 8

3 30

4 50

5 60

样例2 

输入 
6 15

6 5

5 6

6 4

6 6

3 5

7 2

输出 
17