Problem Description

精选矿石（mining）

【题目描述】

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

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

已知你的飞船货舱总载重量上限为 $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$。

所有输入为整数。

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

4 6
2 1
3 4
4 10
3 8

12

Source

2026年山东省信息学体验营