Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
?

CBUYING - Chocolate Buying

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

Được gửi lên bởi:Phan Công Minh
Ngày:2010-02-21
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET
Nguồn bài:USACO Feb 10 - Silver division

hide comments
2018-06-10 10:04:27
bài max nhảm, p[i], c[i] <= 10^18 mà tích nó dùng long long vẫn ăn được.
DKM suýt code bignum
2018-01-17 14:42:17
nhật háo sạch
2017-11-19 15:57:28
không có phạm vi của dữ liệu -> không làm
2017-10-01 07:40:13
Hay lắm bạn =))
Tui cũng bị các QSort ghi lộn longint
2017-09-28 16:45:33


THAM KHẢO THUẬT TOÁN VÀ CODE TẠI:

http://yeulaptrinh.pw/1281/cbuying-spoj/


2017-08-19 11:36:55 Con Bò Huyền Thoại
https://kienthuc24h.com/cbuying-spoj-chocolate-buying/
2017-07-14 13:08:52
int64(long long) được 87.25, Qword(unsigned long long) mới đc 100
2017-01-10 15:05:59
vì cái p[i]*c[i] mà mất 1 đấm
2016-12-28 19:46:19
ez :)
2016-11-30 16:28:41
unsigned long long hết trừ n.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.