题目描述

你驾驶宇宙飞船在星际探险中降落到了一颗小行星上，发现了一堆富矿。经过初步检测，这里共有 $n$ 块非常珍贵的矿石，每块矿石都有一定的重量 $w_i$ 和能量价值 $v_i$。

令人惊奇的是，这些矿石的重量非常接近：最轻的和最重的矿石重量相差不超过 $10$。

已知你的飞船货舱总载重量上限为 $m$，你想在不超过货舱载重的前提下，选取一些矿石带回地球（每块矿石最多只能搬运一次），使得所选矿石的总能量价值最大，请输出这个最大值。

输入格式

第一行两个整数 $n,m$，含义如上。

接下来 $n$ 行，每行两个整数 $w_i,v_i$，分别表示第 $i$ 块矿石的重量和能量价值。

输出格式

一个整数，表示能获得的最大总能量价值。如果一块矿石都装不了（即每块矿石的重量都大于 $m$），输出 $0$。

4 6
2 1
3 4
4 10
3 8

12

4 1000000000
500000002 10
499999997 8
499999996 2
500000004 15 

18

提示

【样例 $1$ 解释】

最优方案：选择矿石 $2$（重 $3$，价值 $4$）和矿石 $4$（重 $3$，价值 $8$），总重 $6$，总价值 $12$。

【数据范围】

$1\le n\le 100$；$1\le m\le 10^9$；$1\le w_i\le 10^9$；$1\le v_i\le 10^7$。

所有输入为整数。

性质 $\mathrm{A}$：$\displaystyle\left(\sum_{\substack{1\le i\le n\\w_i\le m}}w_i\right)\le m$，即重量小于等于 $m$ 的矿石的重量和不超过 $m$。