010 - ナップザック問題(Expert)

問題

価値と重さがそれぞれ v_i, w_i であるような n 個の品物があります。それぞれの荷物には 1 から N の番号が振られています。

これらの品物から、重さの総和が W を超えないように選んだときの、価値の総和の最大値を求めなさい。また、その時に選んだ荷物の番号を列挙しなさい。

入力

1 行目に品物の数 n, 選べる品物の重さの総和 W が半角空白区切りで与えられる。

続く n 行には、それぞれの品物の情報が書かれている。そのうち、i 行目には、空白で区切られた整数 v_i, w_i が書かれており、i 番目の品物の価値が v_i で 重さが w_iであることを表す。

制約

• 1 ≦ n ≦ 100
• 1 ≦ W ≦ 10000
• 1 ≦ v_i ≦ 1000
• 1 ≦ w_i ≦ 1000

出力

1行目に、重さの総和 W を超えないように荷物を選ぶときの価値の総和の最大値を出力する。

2行目に、選んだ荷物の番号を昇順(小さい順) で半角空白区切りで出力する。末端の空白の出力は出力してもしなくてもよい。

また価値の総和が同じになるような荷物の選び方が複数あるとき、どれを出力してもよい。

入出力例

入力例1

4 5
2 3
1 2
3 4
2 2

出力例1

4
1 4

1, 4番目の荷物を選ぶと、重さの総和 5 で、価値の総和が 4 となりこれが最大となる。

入力例2

1 1
451 4

出力例2

0

重さ 1 以下で選べる荷物がないので、0 を出力する。

入力例3

2 10
5 9
4 10

出力例3

5
1