CHOCOLATE BUYING

Nguồn: http://vn.spoj.com/problems/CBUYING/

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.

Dữ liệu vào: từ tệp văn bản CBUYING.INP

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

Dữ liệu ra: ghi vào tệp văn bản CBUYING.OUT

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

Ví dụ:

CBUYING.INP	CBUYING.OUT
5 50 5 3 1 1 10 4 7 2 60 1	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ò.

SOLUTION - CODE