Có ~N~ loại viên đá quý được đánh số từ 1 đến ~N~. Loại viên thứ ~i~ (~1 ≤ i ≤ N~) có khối lượng là ~w_i~, giá trị là ~v_i~ và số lượng rất lớn, được xem như là vô hạn.

Nam định chọn một số viên bỏ vào chiếc túi của anh ta để mang về. Sức chứa tối đa của chiếc túi là ~W~, nghĩa là tổng khối lượng các vật có thể mang tối đa là ~W~.

Hãy tìm tổng giá trị lớn nhất của các viên đá mà Nam có thể mang về nhà.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ (~1 ≤ N ≤ 100~) và ~W~ (~1 ≤ W ≤ 10^3~): số lượng loại đá và sức chứa tối đa của chiếc túi.
• ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~w_i~ (~1 ≤ w_i ≤ W~) và ~v_i~ (~1 ≤ v_i ≤ 10^9~) - lần lượt là khối lượng và giá trị của loại viên đá thứ ~i~.

Output

• Xuất ra tổng giá trị lớn nhất của các viên đá mà Nam có thể mang về nhà.

Ví dụ

Input

3 8
3 30
4 50
5 60

Output

100

Giải thích:

Chọn 2 viên đá loại 2, chúng có trọng lượng là 4 * 2=8 vừa với chiếc túi và giá trị là 50 * 2=100.