Những người em họ của Lan rất thích ăn sô-cô-la, nên bạn Lan quyết định mua một ít cho họ. Siêu thị ABC có ~ n ~ loại sô-cô-la được đánh số từ 1 đến ~ n ~ với số lượng mỗi loại không hạn chế. Loại thứ ~ i ~ có giá ~ p_i ~ (nghìn đồng)/1 gói và có đúng ~ c_i ~ người em họ muốn ăn loại sô-cô-la này. Bạn Lan có ~ k ~ (nghìn đồng) để mua sô-cô-la cho những người em họ.

Yêu cầu: Hãy lập trình cho biết Lan có thể mua được sô-cô-la cho tối đa bao nhiêu người em họ? Biết rằng mỗi người em họ chỉ thích một loại sô-cô-la, và người em họ đó chỉ ăn được loại sô-cô-la ấy.

Dữ liệu vào:

Dòng đầu tiên là hai số nguyên ~ n ~ và ~ k ~ ~ (1≤n≤10^5, 1≤ k ≤ 10^{18}) ~.

N dòng tiếp theo, mỗi dòng là hai số nguyên dương ~ p_i ~ và ~ c_i ~ cách nhau ít nhất một dấu cách ~ (1 ≤ p_i ≤ 10^{18}, 1 ≤ c_i ≤ 10^{18}) ~.

Kết quả ra: Xuất ra màn hình một số nguyên dương là số lượng tối đa người em họ mà bạn Lan có thể mua được sô-cô-la cho họ.

Ví dụ:

Input

5  50
5  3
1  1
10  4
7  2
60  1 

Output

8 

Giải thích: Bạn Lan sẽ mua như sau:

• Mua 3 gói sô-cô-la loại 1 mất 3 * 5= 15 nghìn đồng.
• Mua 1 gói sô-cô-la loại 2 mất 1 * 1= 1 nghìn đồng.
• Mua 2 gói sô-cô-la loại 3 mất 2 * 10= 20 nghìn đồng.
• Mua 2 gói sô-cô-la loại 4 mất 2 * 7= 14 nghìn đồng.
• Tổng cộng hết: 15+1+20+14=50 nghìn đồng và bạn Lan đã mua sô-cô-la được cho 8 người em họ.