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

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à Vi ≤ 100 và giá trị là Pi ≤ 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.

Input: 

• 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ố Vi và Pi cách nhau một dấu cách

Output: 

• 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

Ví dụ

Example

Input:
5 11
3 3
4 4
5 4
9 10
4 4
Output:
11
5 2 1