Những người em họ của Lan rất thích ăn sô-cô-la, nên bạn Lan quyết định mua một ít cho họ. Siêu thị ABC có ~N~ loại sô-cô-la được đánh số từ ~1~ đến ~N~ với số lượng mỗi loại không hạn chế. Loại thứ ~i~ có giá ~P_i~ (nghìn đồng)/gói và có đúng ~C_i~ người em họ muốn ăn loại sô-cô-la này. Bạn Lan có ~K~ (nghìn đồng) để mua sô-cô-la cho những người em họ.
Yêu cầu:
Hãy lập trình cho biết Lan có thể mua được sô-cô-la cho tối đa bao nhiêu người em họ? Biết rằng mỗi người em họ chỉ thích một loại sô-cô-la, và người em họ đó chỉ ăn được loại sô-cô-la ấy.
Dữ liệu vào:
Dòng đầu tiên là hai số nguyên ~N~ và ~K~ (~1 \leq N \leq 10^5, 1\leq K \leq 10^{18}~).
N dòng tiếp theo, mỗi dòng là hai số nguyên dương ~P_i~ và ~C_i~ cách nhau ít nhất một dấu cách (~1 \leq P_i \leq 10^{18}, 1 \leq C_i \leq 10^{18}~).
Kết quả ra
Xuất ra màn hình một số nguyên dương là số lượng tối đa người em họ mà bạn Lan có thể mua được sô-cô-la cho họ.
Sample Input
5 50
5 3
1 1
10 4
7 2
60 1
Sample Output
8
Giải thích: Bạn Lan sẽ mua như sau:
- Mua ~3~ gói sô-cô-la loại ~1~ mất ~3.5=15~ nghìn đồng.
- Mua ~1~ gói sô-cô-la loại ~2~ mất ~1.1=1~ nghìn đồng.
- Mua ~2~ gói sô-cô-la loại ~3~ mất ~2.10=20~ nghìn đồng.
- Mua ~2~ gói sô-cô-la loại ~4~ mất ~2.7=14~ nghìn đồng.
Tổng cộng hết: ~15+1+20+14=50~ nghìn đồng và bạn Lan đã mua sô-cô-la được cho ~8~ người em họ.
Bình luận