=======================================
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
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ò.
=====================================================
Bài này làm tham lam!
Sort tăng theo P....ưu tiên mua cái rẻ....Đơn giản thôi
