文件输入输出

本题采用文件输入输出。

• 输入文件：mining.in
• 输出文件：mining.out

题目描述

你驾驶宇宙飞船在星际探险中降落到一颗小行星上，发现了一堆富矿。这里共有 $n$ 块珍贵矿石，第 $i$ 块矿石的重量为 $w_i$，能量价值为 $v_i$。

这些矿石的重量非常接近：最轻矿石与最重矿石的重量之差不超过 $10$。

飞船货舱的总载重量上限为 $m$。你需要在总重量不超过 $m$ 的前提下选取若干块矿石带回地球，每块矿石最多只能选取一次，使所选矿石的总能量价值最大。

请输出能够获得的最大总能量价值。

输入格式

第一行包含两个整数 $n,m$。

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

输出格式

输出一个整数，表示能够获得的最大总能量价值。

如果一块矿石都装不了，即每块矿石的重量都大于 $m$，输出 $0$。

样例输入 1

4 6
2 1
3 4
4 10
3 8

样例输出 1

12

样例说明 1

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

样例输入 2

4 1000000000
500000002 10
499999997 8
499999996 2
500000004 15

样例输出 2

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$；
• $\max(w_i)-\min(w_i)\le 10$；
• 所有输入均为整数。

性质 A：所有满足 $w_i\le m$ 的矿石的重量之和不超过 $m$，即