THỰC HÀNH

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à M kg vàng và trên đảo có N thỏi vàng, thỏi thứ i có khối lượng w_i và giá trị v_i. 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ố N, M 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.
• N dòng tiếp theo, dòng thứ i + 1 chứa hai số nguyên dương là trọng lượng và giá trị của thỏi vàng thứ i.

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ứ 1 và thứ 3 thì trổng trọng lượng là 4 và tổng giá trị là 10

Giới hạn: Trong tất cả các test: 1 ≤ M ≤ 10⁴, 1 ≤ w_i, v_i ≤ 10⁴

• 40% số test (ứng với 40% số điểm của bài) 1 ≤ N ≤ 10
• 40% số test (ứng với 40% số điểm của bài) 10 < N ≤ 20
• 20% số test (ứng với 20% số điểm của bài) 20 < N ≤ 40.