Chuột Mickey tỉnh dậy khi bố mẹ đã đi làm, chú rất đói bụng và tìm xem bữa sáng của mình ở đâu. Chú tìm thấy một tờ giấy mẹ dán trên cánh cửa có nội dung:

“Con trai ngoan của mẹ, con hãy mở cửa ra và sẽ nhìn thấy những miếng pho-mát béo ngậy. Mỗi miếng pho-mát có trọng lượng là w, nhưng để lấy nó mang về nhà con sẽ mất thời gian là t.Có những miếng pho mát ở ngay cạnh con( t=0) và có những miếng pho-mat lại ở rất xa. Mỗi lần con chỉ được đi ra và lấy một miếng pho-mát mang về nhà. Con hãy tìm cách mang về nhà những miếng pho-mát có tổng trọng lượng lớn nhất sao cho tổng thời gian lấy chúng không được vượt quá L. Những miếng pho-mát con mang về nhà là bữa sáng của của con đấy !”.

Mickey rất đói bụng nhưng loay hoay mãi không tìm cách nào tối ưu để lấy được những miếng pho-mát về cho bữa sáng.

Yêu cầu: Em hãy giúp Mickey giải bài toán hóc búa trên.

Dữ liệu: Vào từ file văn bản PHOMAT.INP có cấu trúc:

• Dòng đầu tiên chứa hai số nguyên dương N, L (0< N £ 100; 0< L 100). Trong đó N là số miếng pho-mát, L là thời gian giới hạn để lấy những miếng pho-mát;
• Dòng thứ i trong N dòng tiếp theo chứa hai số nguyên dương t_i, w_i (0£ t_i £ 1000, 0< w_i  10⁵). Trong đó t_i là thời gian để lấy miếng pho-mát i mang về nhà, w_i là trọng lượng của miếng pho-mát.

Kết quả: Đưa ra file văn bản PHOMAT.OUT chứa một số duy nhất là tổng trọng lượng lớn nhất của các miếng pho-mát lấy được.

Ví dụ: