Hẳn chúng ta ai cùng biết truyện cổ tích Cây Khế (hay là truyện ăn khế trả vàng). Ở đoạn kết của câu truyện, khi người anh mang theo túi ba trăm gang được chim chở ra đảo vàng, người anh 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 anh 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 wi và giá trị vi. 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: Cho trong tệp tin văn bản ANKHE.INP gồm

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 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: Ghi ra tệp tin văn bản ANKHE.OUT gồm

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ụ:

ANKHE.INP

3 4
1 4
2 5
3 6

ANKHE.OUT

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 có: 1≤M,w_i,v_i≤10^4. 

    40% số test (ứng với 40% số điểm của bài) có 1≤n≤10; 

    40% số test khác (ứng với 40% số điểm của bài) có 10≤n≤20; 

    20% số test còn lại (ứng với 20% số điểm của bài) có 20≤n≤40.