题目描述

有 $N$ 个物品，编号 $1,2, \dots ,N$。

对于每个 $i$（$1 \le i \le N$），物品 $i$ 的重量是 $w_i$，价值是 $v_i$。 今要从这 $N$ 个物品中拿一些放进背包。背包的容量是 $M$，拿的物品的重量之和不能超过 $M$。 求放进背包的物品的价值之和的最大值。 限制

输入的值都是整数。 $1 \le N \le 100$

$1 \le M \le 10^9$

$1 \le w_i \le M$

$1 \le v_i \le 10^3$

输入格式

$N$ $M$

$w_1$ $v_1$

$w_2$ $v_2$

$\vdots$

$w_N$ $v_N$

输出格式

输出答案。

3 8

3 30

4 50

5 60

90