CBUYING - Chocolate Buying
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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 tiền và có đúng C_i con bò muốn ăn loại Sô-cô-la ấy. Farmer John có B tiền để 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ò.
- Người up: company_1
- Nguồn bài: USACO Feb 10 - Silver division