A. SOCOLATE - Mua Sô-cô-la

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản

Đề bài

Để 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ó N\ (1≤N≤10^5) loại sô-cô-la khác nhau, đánh số 1, 2, \ldots, N , với số lượng được xem là vô hạn (đủ đáp ứng mọi nhu cầu). Loại sô-cô-la thứ i có giá là a_i\ (1≤a_i≤10^{18}) 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à B\ (1≤B≤10^{18}) để 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 N B ;
  • N dòng tiếp theo, dòng thứ i ghi hai số nguyên a_i, b_i .

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 3 thanh sô-cô-la loại 1 , 1 thanh sô-cô-la loại 2 , 2 thanh sô cô la loại 3 , 2 thanh sô-cô-la loại 4 . Như vậy tổng số tiền phải trả là 3\times 5+1\times 1+2\times 10+2\times 7=50 (vừa đủ tiền) và số bạn nữ nhận được là 3+1+2+2=8 bạn. Đây là phương án mua tối ưu.