Tý có một tên trộm đột nhập vào cửa hàng có \(N\) món đồ. Món đồ \(i\) có trọng lượng \(w_i\) và giá trị \(v_i\). Chiếc ba lô của hắn chỉ chịu được tổng trọng lượng tối đa \(W\).

Hãy tìm cách chọn các món đồ ba lô sao cho tổng giá trị là lớn nhất.

Định dạng đầu vào

• Dòng đầu chứa N và W\( (\)1 \le N \le 50\(, \)1 \le W \le 10^4~).
• \(N dòng tiếp theo, mỗi dòng chứa w_i và v_i\) (\(1 \le w_i \le 100\), ~1 \le v_i \le 10^3).

Định dạng đầu ra

• Một số nguyên duy nhất là tổng giá trị lớn nhất tìm được.

Ví dụ

Input:

4 10
5 10
4 40
6 30
3 50

Output:

90

Ràng buộc