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á Pi $$ và có đúng Ci con bò muốn ăn loại Sô-cô-la ấy. Farmer John có B $$ để 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 Pi và Ci.
Output
Gồm một số duy nhất là kết quả.
Input:
5 50
5 3
1 1
10 4
7 2
60 1
Output:
8
Giới hạn
1<=N<=10^5
1 <= B <= 10^18
1 <= Ci <= 10^18
1 <= Pi <= 10^18.
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ò.