← 返回比赛
已结束 GESP排位赛#12
← 上一题 下一题 →

A3169 | 火星背包 II

来源官方 / 2024
时间限制2s
内存限制512MB
通过 / 提交0/0

题目描述

时间限制：2000ms

内存限制：512MB


在遥远的火星矿场上，有 $N$ 块重量和价值分别为 $w_i(1 \le i \le N)$ 和 $v_i(1 \le i \le N)$ 的矿石。

这些矿石都是相当巨大且沉重，以至于普通的背包难以装载。
不过，在这个星球上有一种特殊的背包，我们称之为 「$\bf{火星背包}$」，它能够承载总重量不超过 $M$ 的矿石。

这次发现的矿石价值都比较低，但是基地的装置可以将这些矿石再加工使其体积和重量变小，所以你依然需要尽可能多地收集矿石，并且使收集到的矿石总价值尽可能的高。

你的任务是找到一种方法，在不超过背包承载能力的情况下，选取矿石，使得它们的总价值最高。

$\large{数据范围}$

- $1 \le N \le 10^3$
- $1 \le v_i \le 100$
- $1 \le w_i \le M \le 10^9$

输入格式

对于每个测试文件格式如下：

$\tt{N\ M}$

$\tt{w_1\ v_1}$
$\tt{w_2\ v_2}$
$\vdots$
$\tt{w_N\ v_N}$

输出格式

对于每个测试文件，在单独的一行输出能够选取矿石的最大价值总和。

输入输出样例

输入 #1
4 5
2 3
1 2
3 4
2 3
输出 #1
8
输入 #2
9 110
19 31
17 23
44 86
18 14
4 4
34 73
17 56
7 88
24 44
输出 #2
307
C++ 编辑器
输入
输出