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)/1 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ọ.

Ví dụ:

Input		Output
5 50 5 3 1 1 10 4 7 2 60 1		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ọ.