6668: 01背包路径 I
[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
最大价值为 $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$ 件物品。
Sample 3 Input
5 5
1 2
2 4
3 4
3 4
4 5
Sample 3 Output
8
2 4
最大价值为 $8$，选择第 $2$ 件和第 $4$ 件物品也符合要求。