输出方案的背包决策

题目描述

探险日志要求记录下每次装载的物品列表。背包容量为 $W$，有 $n$ 件物品，每件物品有体积和价值，只能取或不取。你的目标是在不超过容量的前提下使总价值最大，并输出一组达到最大价值的物品编号。

物品编号按输入顺序为 $1\sim n$。若存在多种最优方案，可输出任意一种；若最优方案为空集，第二行输出空行即可。

输入格式

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

接下来 $n$ 行，每行包含两个整数，表示一件物品的体积与价值。

输出格式

输出两行：

• 第一行输出一个整数，为可获得的最大总价值；
• 第二行输出一行，包含一组达到该价值的物品编号，按升序用空格分隔；若不选任何物品则输出空行。

输入输出样例 #1

输入 #1

4 7
3 5
2 4
4 6
5 7

输出 #1

11
2 3

数据范围

对于 $100\%$ 的数据，$1 \le n \le 200$，$1 \le W \le 2000$，体积与价值均在 $[1,10^4]$。EOF