Mua hàng

Trong một cửa hàng có \(n\) gói hàng, gói hàng thứ \(i\) có trọng lượng là \(W_i\) và giá trị là \(V_i\) (\(W_i,V_i \le 100\)). Bạn Nam vào cửa hàng để mua hàng, sức của Nam không thể mang vượt quá \(M\). Hỏi Nam sẽ mua các gói hàng như thế nào để được tổng giá trị lớn nhất.

Input

Dữ liệu vào: Từ tệp MUAHANG.INP có cấu trúc:

• Dòng đầu gồm hai số nguyên \(n\) và \(M\) (\(n \le 10^{6},\ M \le 10^{6}\))
• Trên \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(W_i\) và \(V_i\) (\(1 \le W_i, V_i \le 100\)) --- trọng lượng và giá trị của gói hàng thứ \(i\).

Output

Kết quả: Ghi ra tệp MUAHANG.OUT một số duy nhất: tổng giá trị lớn nhất mà Nam có thể mua được.

Example

3 4
1 4
2 5
3 6

10

Scoring

• Có \(60\%\) số test ứng với \(60\%\) số điểm của bài có \(1 \le n, M \le 100\).
• Có \(20\%\) số test ứng với \(20\%\) số điểm của bài có \(100 < n, M \le 10^{3}\).
• Có \(20\%\) số test ứng với \(20\%\) số điểm của bài có \(10^{3} < n, M \le 10^{6}\).