Vì quá tham lam nên người anh bị rơi xuống biển, không mang được châu báu về nhà. Vợ người anh ở nhà buồn phiền vì nhớ chồng nên đã đem con đi tìm chồng biệt xứ. Lúc này trong làng có cậu Tèo em không có nhà nên được người em cho đến đây ở để quản lý nhà cửa và cây khế cho anh trai trong khi gia đình anh trai chưa về.

Vì thích khế ở đây nên chim thần lại đến. Lần này chim thần chở Tèo em đến đảo đá quý. Trên hòn đảo có \(N\) viên đá quý. Viên thứ \(i\) có trọng lượng là \(w_i\) và có giá trị là \(v_i\). Tèo em mang theo túi năm gang có thể chứa tối đa trọng lượng là \(M\). Hỏi tổng giá trị tối đa của các viên đá quý mà Tèo em có thể mang về là bao nhiêu?

Dữ liệu vào

• Dòng đầu tiên ghi hai số \(N\) và \(M\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) ghi hai số \(w_i\) và \(v_i\) lần lượt là trọng lượng và giá trị của viên đá quý thứ \(i\).

Dữ liệu ra

• Ghi ra một số nguyên duy nhất là tổng giá trị lớn nhất mà Tèo em có thể mang về.

Ràng buộc

• \(1 \le N \le 100\)
• \(1 \le M \le 10^9\)
• \(0 \le w_i \le 10^9\)
• \(0 \le v_i \le 10^3\)

Input 1

3 8
3 30
4 50
5 60

Output 1

90

Input 2

1 1000000000
1000000000 10

Output 2

10