题目描述

有 $n$ 个物品，编号为 $i$ 的物品的重量为 $w_i$，价值为 $v_i$，

现在要从这些物品中选一些物品装到一个载重为 $m$ 的背包中，使得背包内物体在总重量不超过 $m$ 的前提下价值尽量大。

输入格式

输入第一行包含两个正整数 $n$ (物品数量) 和 $m$ (背包载重)。 接下来 $n$ 行，每行二个整数 $w_i，v_i$，表示每个物品的重量和价值。

输出格式

输出一个正整数表示最大价值

4 6
1 4
2 6
3 12
2 7

23

数据规模与约定

对于 $100\%$ 的数据, $2\le n\le 3500，m\le 12880，1\le w_i，v_i\le 1000$