Trong truyện cổ tích "Cây Khế" ta đã biết rằng chim thần chở người anh với một cái túi ba gang đến hòn đảo đầy vàng bạc châu báu. Người em băn khoăn không biết chọn đồ vật nào cho vào túi vì chỉ có một cái túi ba gang..
Giả sử rằng trên hòn đảo kia có N đồ vật khác nhau, đồ vật thứ i có giá trị là ai và có thể tích là bi. Cũng giả sử rằng cái túi mà người em mang đi chỉ có thể tích là M. Bạn hãy giúp người em chọn ra trong N đồ vật trên một số đồ vật sao cho tổng thể tích của các đồ vật được chọn không vượt quá M và tổng giá trị các đồ vật được chọn là lớn nhất.
Input: Cho trong file văn bản CAYKHE.INP
Output: Ghi ra file văn bản CAYKHE.OUT
CAYKHE.INP |
CAYKHE.OUT |
5 10 20 3 19 1 30 7 24 3 15 6 |
63 3 1 2 4 |