Chọn trái cây

Vào dịp nghỉ hè hằng năm, Lan được ba mẹ cho về thăm ngoại và thư giãn sau một năm học tập khá vất vả. Cuối chuyến nghỉ hè, Lan thường xin ngoại một số trái cây có sẵn trong vườn mang về, trước làm quà cho bố mẹ, sau đó bán lại lấy chi phí mua sách tham khảo hỗ trợ việc học. Biết rằng có n trái cây ( n <= 50), mỗi trái cây có trọng lượng là Wi (Wi <= 20) và trị giá Vi(Vi <= 50). Do sức khỏe giới hạn nên Lan chỉ được mang một giỏ chứa đựng tối đa P (P <=100). Bạn hãy giúp Lan chọn các loại trái cây mang về sao cho trọng lượng tương ứng với giỏ và được tổng giá trị là lớn nhất.
Input : Tập tin văn bản GIO.INP
    Dòng 1: Chứa hai số n, P cách nhau ít nhất một dấu cách;
    N dòng tiếp theo, dòng I chứa hai số nguyên dương Wi , Vi cách nhau ít nhất một dấu cách.
Output: File văn bản GIO.OUT
    Dòng 1: Ghi giá trị lớn nhất Lan có thể lấy;
    Dòng 2: Ghi chỉ số các trái cây Lan chọn lấy.
VD:
        GIO.INP                          GIO.OUT
           5 12                                   18
           3 4                                     5 4 2
           2 5
           9 10
           6 7
           3 6
VD 2:
       GIO.INP                           GIO.OUT
          7 50                                   100
         13 12                                  7 6 5 4
         15 14
         18 15
         19 20
         21 17
         3 26
         7 37

                                                           Lời giải tham khảo