A19337.火星背包

时间限制：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$：

选取矿石 $[1, 2, 4]$ 需要的背包容量为 $2 + 1 + 2 = 5$，价值为 $3 + 2 + 3=8$。
无法通过选取其他矿石在背包容量允许的情况下，得到更大的价值。