6669: 01背包路径 II
[Creator : ]
Description
一个旅行者有一个最多能装 $M$ 公斤的背包，现在有 $n$ 件物品，编号从 $1 \sim n$，它们的重量分别是 $W_1,\ W_2,\ ...,\ W_n$，它们的价值分别为 $C_1,\ C_2,\ ...,\ C_n$。
求旅行者能获得最大总价值，以及组成这个价值的具体物品编号。
求旅行者能获得最大总价值，以及组成这个价值的具体物品编号。
Input
第一行：两个整数，$M$（背包容量，$M≤1000$）和 $N$（物品数量，$N≤1,000$）；
第二到 $N+1$ 行：每行二个整数 $W_i\ (0 < W_i \leq 100),\ C_i\ (0<C_i≤1,000)$，表示第 $i$ 个物品的重量和价值。
第二到 $N+1$ 行：每行二个整数 $W_i\ (0 < W_i \leq 100),\ C_i\ (0<C_i≤1,000)$，表示第 $i$ 个物品的重量和价值。
Output
一共两行。
第一行，一个数，表示最大总价值。
第二行包括若干个数，表示具体的方案，第 $i$ 个数表示物品的编号。
方案的编号是唯一，要求字典序最小。
第一行，一个数，表示最大总价值。
第二行包括若干个数，表示具体的方案，第 $i$ 个数表示物品的编号。
方案的编号是唯一，要求字典序最小。
Sample 1 Input
10 4
2 1
3 3
4 5
7 9
Sample 1 Output
12
2 4
Sample 2 Input
5 5
1 2
2 4
3 4
3 4
4 5
Sample 2 Output
8
2 3
最大价值为 $8$，可以选择 $2,3$ 或者 $2,4$，但是字典序最小为 $2,3$。
Sample 3 Input
5 4
1 2
2 4
3 4
4 6
Sample 3 Output
8
1 4
$2,3$ 和 $1,4$ 都可以构成总价值 $5$ 的方案，但是 $1,4$ 字典序最小。