暂无测试数据。

Bessie 去珠宝商店想要买一些魔法宝石。商店里有 $n$ 个宝石，每个宝石的重量为 $w_i$，幸运值为 $v_i$。Bessie 的购物车只能装重量之和不超过 $m$ 的商品，现在她想知道如何选择宝石，能让购买的幸运值之和最大。

输入格式

第一行两个整数 $n,m$，表示宝石的数量和购物车的承重能力。

接下来 $n$ 行，每行两个整数 $w_i,v_i$，表示每个宝石的重量和幸运值。

输出格式

输出一个整数，表示幸运值之和最大值。

数据范围

$1\le n\le 3000$，$1 \le m\le 10000$，$1\le w_i,v_i \le 100$

4 6
1 4
2 6
3 12
2 7

23