Để kỷ niệm những ngày tháng cuối cùng của tuổi học trò, các bạn nam khối 12 quyết định sẽ góp tiền mua sô-cô-la tặng các bạn nữ nhân ngày Valentine (14-02) mỗi bạn nữ sẽ nhận được một thanh sô-cô-la. Sau khi đăng tải thông tin này lên Facebook, tất cả các bạn nữ đều vui mừng và thông báo loại sô-cô-la mà mình yêu thích.
Cửa hàng bán sô-cô-la cạnh trường có loại sô-cô-la khác nhau, đánh số , với số lượng được xem là vô hạn (đủ đáp ứng mọi nhu cầu). Loại sô-cô-la thứ có giá là cho một thanh và theo kết quả đăng ký thì sẽ có $b_i\ (1≤b_i≤10^{18}) bạn nữ thích ăn loại sô-cô-la này.
Sau khi quyên góp số tiền tiết kiệm được, các bạn nam đã có được một quĩ là để mua sô-cô-la. Hãy giúp Hùng-trưởng ban tổ chức tính xem số lượng lớn nhất các bạn nữ có thể nhận được quà từ các bạn nam. Biết rằng các bạn nữ chỉ nhận quà tặng là loại sô-cô-la mà cô ta thích (cô ta thà không có sô-cô-la chứ nhất định không lựa chọn loại khác).
Dữ liệu:
Dòng đầu tiên ghi hai số nguyên dương và ;
dòng tiếp theo, dòng thứ ghi hai số nguyên .
Các số nguyên trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.
Kết quả:
Ghi ra một số nguyên duy nhất là số lượng lớn nhất các bạn nữ được tặng quà.
Ví dụ:
Dữ liệu:
5 50
5 3
1 1
10 4
7 2
60 1
Kết quả:
8
Giải thích:
Mua thanh sô-cô-la loại , thanh sô-cô-la loại , thanh sô cô la loại , thanh sô-cô-la loại . Như vậy tổng số tiền phải trả là (vừa đủ tiền) và số bạn nữ nhận được là bạn. Đây là phương án mua tối ưu.
