Có ~N~ viên đá quý được đánh số từ 1 đến ~N~. Viên thứ ~i~ (~1 ≤ i ≤ N~) có khối lượng là ~w_i~ và giá trị là ~v_i~.

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à. Biết rằng Nam được lấy một phần của viên đá.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ (~1 ≤ N ≤ 10^5~) và ~W~ (~1 ≤ W ≤ 10^3~): số lượng viên đá 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 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à. Kết quả làm tròn đến số nguyên.

Ví dụ

Input

3 8
3 30
4 50
5 60

Output

98

Giải thích:

Chọn viên đá thứ hai và 4/5 phần viên đá thứ 3, chúng có trọng lượng là 4 + 5 * 4/5 = 8 vừa với chiếc túi và giá trị là 50 + 60 * 4/5 = 98.