Trường THPT Chuyên Hoàng Văn Thụ - Hòa Bình

Một thằng trộm lọt vào một siêu thị. Hắn mang theo một cái túi để đựng đồ ăn trôm được.

Trong siêu thị có N đồ vật (1 <= N <= 15), trong đó đồ vật thứ i có thể tích là V[i] và giá trị là W[i]. Cái túi của thằng trộm chỉ đựng được tổng thể tích tối đa là M.

Thằng trộm cần chọn đồ vật nào để mang đi với tổng giá trị là lớn nhất mà không bị rách túi.

Input: 

-         Dòng 1 chứa hai số nguyên dương N và M

-         N dòng tiếp theo,  dòng thứ i là 2 số V[i] và W[i]

Output: 

-         Dòng 1 là tổng giá trị lớn nhất của các đồ vật mang đi

-         Các dòng tiếp theo, mỗi dòng chứa một số là chỉ số của đồ vật cần mang đi.

INPUT:

5 10
3 20
1 19
7 30
3 24
6 15

OUTPUT:

63
1
2
4