Hẳn chúng ta ai cùng biết câu truyện cổ tích Cây Khế (hay là câu truyện ăn khế trả vàng). Ở đoạn kết của câu truyện, khi người em mang theo túi ba trăm gang được chim chở ra đảo vàng, người em vô cùng lúng túng không biết làm sao để chọn được những thỏi vàng cho vừa túi mà tổng giá trị lớn nhất, lấy thỏi nào, bỏ thỏi nào, vấn đề phức tạp đây. Em hãy viết chương trình giúp người em nhanh chóng lựa chọn vàng để chim chở về chứ cứ ở ngoài đảo lâu mà gặp bão to thì nguy.
Cho biết cái túi đựng được tối đa là kg vàng và trên đảo có thỏi vàng, thỏi thứ có khối lượng và giá trị . Hãy xác định giá trị lớn nhất của số vàng mà túi đựng được (không vượt quá trọng lượng tối đa của túi có thể đựng được).
Dữ liệu vào:
Dòng đầu là hai số lần lượt là số thỏi vàng trên đảo và tải trọng tối đa của túi;
dòng tiếp theo, dòng thứ chứa hai số nguyên dương là trọng lượng và giá trị của thỏi vàng thứ .
Dữ liệu ra:
Gồm một dòng duy nhất ghi số nguyên không âm là đáp số bài toán.
Ví dụ:
Dữ liệu vào:
3 4
1 4
2 5
3 6
Dữ liệu ra:
10
Giải thích:
Ta chọn thỏi vàng thứ và thứ thì trổng trọng lượng là và tổng giá trị là .
