Để 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 loại sô-cô-la khác nhau, đánh số 1, 2, …, , 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] cho một thanh và theo kết quả đăng ký thì sẽ có b[i] 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 để mua sô-cô-la.

Yêu cầu: Tính 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 và B ( 1 ≤ n ≤ 10^5, 1 ≤ B ≤ 10^18);

• n dòng tiếp theo, dòng thứ ghi i hai số nguyên a[i] và b[i] (1 ≤ a[i], b[i] ≤ 10^18).

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

Sample Input

5 50
5 3
1 1
10 4
7 2
60 1

Sample Output

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à 5x3 + 1x1 + 10x 2 + 7x 2 = 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.