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ò.

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ả.

Example

Input  

5 50  
5 3  
1 1  
10 4  
7 2  
60 1  
  
Output  
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<=N<=10^5
• 1 <= B <= 10^18
• 1 <= C_i <= 10^18
• 1 <= P_i <= 10^18.