CBUYING spoj – Chocolate Buying

Nguồn đề bài: http://vn.spoj.com/problems/CBUYING/

1. Đề bài CBUYING spoj

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 hạn

1<=N<=10^5
1 <= B <= 10^18
1 <= C_i <= 10^18
1 <= P_i <= 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ò.

###################################################

2. Hướng dẫn CBUYING spoj

– Bạn sẽ dễ dàng nhận thấy, cứ ưu tiên mua cho những con bò có bánh yêu thích rẻ hơn thì bạn sẽ được khoản còn lại nhiều hơn. chính vì vậy ở đây chỉ cần sắp xếp C[i], P[i] theo P[i] là được. Tức là ưu tiên mua bánh giá rẽ trước