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

A1819 | 火星背包

时间限制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 40$
- $1 \le w_i, v_i, M \le 10^{15}$
- $1 \le w_i \le M$

输入格式

对于每个测试数据格式如下：

$N$ $M$

$w_1$ $v_1$
$w_2$ $v_2$
$\vdots$
$w_N$ $v_N$

输出格式

答案的第一行为挑选的矿石总价值和数量。
第二行为挑选的矿石的编号。

若有多种最优方案，输出任意一种即可。

输入输出样例

输入 #1
4 5
2 3
1 2
3 4
2 3
输出 #1
8 3
1 2 4
输入 #2
9 110
19 131
17 123
44 186
18 14
4 4
34 73
17 56
7 188
24 144
输出 #2
697 5
2 3 7 8 9
C++ 编辑器
输入
输出