Trong siêu thị có n gói hàng, gói hàng thứ I có trọng lượng là Wi<=100 và giá trị Vi<=100. Một tên trộm đột nhập vào siêu thị, sức của tên trộm không thể mang được trọng lượng vượt quá M (M<=100). Hỏi tên trộm sẽ lấy đi những gói hàng nào để được tổng giá trị lớn nhất
Dữ liệu: vào từ tệp CAITUI.INP gồm:
+ Dòng đầu tiên gồm 2 số nguyên n và m (n<=40,m<=100).
+ n dòng tiếp theo, mỗi dòng chứa 2 số nguyên Wi, Vi (Wi, Vi<=100) lần lượt là trọng lượng và giá trị của gói hàng thứ i.
Kết quả: ghi ra tệp CAITUI.OUT là giá trị lớn nhất tên trộm lấy được.
Ví dụ:
|
CAITUI.INP |
CAITUI.OUT |
|
3 4 1 4 2 5 3 6 |
10
|