Lần đầu tiên Hải được bố mẹ cho đi du lịch bằng máy bay. Hải phấn khởi chuẩn bị vali để chứa nhiều dùng cá nhân. Đồ vật thứ i có trọng lượng là w_i và giá trị sử dụng là v_i. Khi làm thủ tục lên máy bay ở sân bay, nhân viên thông báo hành lí xách tay vượt quá trọng lượng cho phép nên yêu cầu Hải phải chọn một số đồ dùng thật cần thiết để lại trong vali, số còn lại chuyển sang hành lý dạng kí gửi nhằm đảm bảo trọng lượng hành lí xách tay theo quy định và an toàn cho chuyến bay.

Yêu cầu: Hãy cho biết Hải cần chọn những đồ dùng cần thiết nào để lại trong vali.

Dữ liệu vào: Đọc từ file BAG.INP gồm:

- Dòng 1: chứa 2 số nguyên n và m lần lượt là số đồ dùng và trọng lượng hành lý xách tay cho phép mang lên máy bay (n ≤ 50, m ≤ 100)

- n dòng tiếp theo, mỗi dòng chứa hai số nguyên dương w_i và v_i (w_i, v_i ≤ 100) lần lượt là trọng lượng và giá trị sử dụng của đồ vật thứ i.

Dữ liệu ra: Ghi ra file BAG.OUT gồm

• Dòng 1: Tổng giá trị sử dụng lớn nhất của các đồ vật được chọn để lại trong vali.
• Dòng 2: Ghi chỉ số các đồ vật đc chọn để lại trong vali
• Dòng 3: Ghi tổng trọng lượng các đồ vật đc chọn để lại trong vali

Ví dụ: