该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

精选矿石

题目描述

你驾驶宇宙飞船在星际探险中降落到了一颗小行星上，发现了一堆富矿。经过初步检测，这里共有 $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

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

4 1000000000
500000002 10
499999997 8
499999996 2
500000004 15

18

数据范围

$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$