路径复原 I

题目描述

在一个古老的地牢中，你发现了一个容量为 $M$ 的宝箱，以及 $N$ 件各具特色的宝物。

每件宝物的属性如下：

• 重量 $w_i$。
• 价值 $v_i$。

你当然想要带走总价值最大的宝物组合。但这次，守卫者不仅要求你回答最大价值是多少，还要求你列出所有被选中的宝物编号。

为了使结果唯一，如果存在多种方案都能达到最大价值，请输出字典序最小的宝物编号序列。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示宝物数量和宝箱容量。

接下来的 $N$ 行，每行包含两个整数 $w_i$ 和 $v_i$，表示第 $i$ 件宝物的重量和价值（编号从 1 开始）。

输出格式

第一行输出一个整数，表示最大总价值。

第二行输出若干个由空格隔开的整数，表示被选中的宝物编号，按编号升序排列。

输入输出样例 #1

输入 #1

4 5
1 2
2 4
3 4
4 6

输出 #1

8
1 4

样例 1 说明

选择第 1 件（重 1，值 2）和第 4 件（重 4，值 6），总重 5，总值 8。 也可以选择第 2 件和第 3 件，总重 5，总值 8。 比较编号序列 [1, 4] 和 [2, 3]，字典序最小的是 1 4。

数据范围

对于 $100\%$ 的数据，$1 \le N \le 1000$，$1 \le M \le 1000$，$1 \le w_i, v_i \le 1000$。

建议

三刷