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\)..\(N\)) với số lượng mỗi loại không hạn chế. Loại thứ \(i\) có giá \(P_i\) và có đúng \(C_i\) con bò muốn ăn loại Sô-cô-la ấy. Farmer John có \(B\) để mua Sô-cô-la cho lũ bò.

Yêu cầu: 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.

Dữ liệu vào

• 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\).

Kết quả

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

Sample Input 1

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

Sample Output 1

8

Giải thích
FJ sẽ mua như sau:

+Mua 3 gói sô-cô-la loại 1 mất 3*5= 15$.

+Mua 1 gói sô-cô-la loại 2 mất 1*1= 1$.

+Mua 2 gói sô-cô-la loại 3 mất 2*10= 20$

+Mua 2 gói sô-cô-la loại 4 mất 2*7= 14$.

Tổng cộng hết :15+1+20+14=50$, và FJ đã phục vụ được 8 con bò.

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}\)

Nguồn: SPOJ