Balo nặng trĩu gồm nhiều món quà của gia đình, người thân, bạn bè, đặc biệt là các vật dụng mẹ đã tự tay làm cho Hoàng kèm theo những lời dặn dò đầy tình thương yêu nên Hoàng cố gắng mang theo tất cả. Nhưng trọng lượng balo cho phép sử dụng có giới hạn, loay hoay mãi chưa biết phải xử lý thế nào thì người trưởng đoàn đã đề nghị Hoàng lựa chọn những món quà, vật dụng thực sự cần thiết phải sử dụng trên xe để lại trong balo, số còn lại sẽ gửi vào xe phục vụ để việc di chuyển thuận tiện hơn.

Yêu cầu: Cho biết Hoàng sẽ chọn những món quà, vật dụng cần thiết nào có tổng giá trị sử dụng lớn nhất để lại trong balo sao cho tổng trọng lượng của chúng không vượt quá trọng lượng balo cho phép.

Dữ liệu

• Dòng thứ nhất chứa hai số ~n, m~ (~n \le 50~, ~m \le 10^4~) lần lượt là số món quà, vật dụng và trọng lượng tối đa mà balo cho phép sử dụng.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~c_i~ (~c_i < 10^4~), ~p_i~ (~p_i < 10^4~) là trọng lượng và giá trị sử dụng của món quà, vật dụng thứ ~i~.

Kết quả

• Dòng thứ nhất: ghi tổng giá trị sử dụng lớn nhất của các món quà, vật dụng được Hoàng chọn để lại trong balo.
• Dòng thứ hai: ghi chỉ số của những món quà, vật dụng được Hoàng chọn để lại trong balo (theo thứ tự giảm dần).
• Dòng thứ ba: ghi tổng trọng lượng các món quà, vật dụng được Hoàng chọn để lại trong balo.

Nếu có nhiều cách chọn cùng đạt tổng giá trị lớn nhất thì in một cách chọn bất kỳ.

Ví dụ

BL.INP

6 19
3 3
4 4
5 4
4 6
3 8
9 1

BL.OUT

25
5 4 3 2 1
19

Giải thích: Chọn các món 5, 4, 3, 2, 1 với tổng trọng lượng ~3+4+5+4+3 = 19~ và tổng giá trị ~8+6+4+4+3 = 25~.