Những con bò rất thích ăn Sô-cô-la, nên Farmer John quyết định mua một ít cho chúng.

Cửa hàng có ~N~ loại sô-cô-la (được đánh số từ ~1 \dots N~) với số lượng mỗi loại không hạn chế. Loại thứ ~i~ có giá ~P_i~ tiền và có đúng ~C_i~ con bò muốn ăn loại Sô-cô-la ấy. Farmer John có ~B~ tiền để mua Sô-cô-la cho lũ bò.

Hỏi số bò tối đa mà Farmer John có thể phục vụ là bao nhiêu? Biết rằng mỗi con bò chỉ thích một loại sô-cô-la, và nó chỉ được ăn loại sô-cô-la ấy.

Input

Dòng đầu tiên là hai số nguyên ~N~ và ~B~.

~N~ dòng tiếp theo, dòng thứ ~i + 1~ là hai số nguyên dương ~P_i~ và ~C_i~.

Output

Gồm một số duy nhất là kết quả.

Giới hạn

• ~1 \le N \le 10^{5}~
• ~1 \le B \le 10^{18}~
• ~1 \le C_i \le 10^{18}~
• ~1 \le P_i \le 10^{18}~

Sample Input

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

Sample Output

8

Note

Farmer John sẽ mua như sau:

• Mua ~3~ gói sô-cô-la loại ~1~ mất ~3 \times 5 = 15\$~.
• Mua ~1~ gói sô-cô-la loại ~2~ mất ~1 \times 1 = 1\$~.
• Mua ~2~ gói sô-cô-la loại ~3~ mất ~2 \times 10 = 20\$~.
• Mua ~2~ gói sô-cô-la loại ~4~ mất ~2 \times 7 = 14\$~.