Một tên trộm lọt được vào một gia đình. Hắn mang theo một cái túi có thể tích M để đựng đồ ăn trộm. Trong nhà có n vật dụng (n ≤ 100), vật thứ i có thể tích là V_i ≤ 100 và giá trị là P_i ≤ 100. Vậy tên trộm phải chọn những vật nào để lấy đi mà tổng giá trị của các vật đó là lớn nhất.

Dữ liệu vào:

• Dòng 1: Chứa hai số n, M cách nhau một dấu cách
• N dòng tiếp theo mỗi dòng i ghi hai số V_i và P_i cách nhau một dấu cách

Kết quả ra:

• Dòng 1: Ghi tổng giá trị lớn nhất mà tên trộm có thể lấy được
• Dòng 2: Ghi chỉ số những vật dụng bị lấy đi