Đề bài

Những bạn nữ rất thích ăn sô-cô-la, nên Hoàng quyết định mua một ít cho các bạn ấy. Cửa hàng 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á c{~i~} tiền và có đúng b{~i~} bạn nữ muốn ăn loại sô-cô-la ấy. Hoàng có ~m~ tiền để mua sô-cô-la cho các bạn.

Hỏi số bạn nữ tối đa mà Hoàng có thể phục vụ là bao nhiêu, biết rằng mỗi bạn chỉ thích một loại sô-cô-la và chỉ được ăn loại đó.

Input

Dòng 1: hai số nguyên n và m (1 ≤ ~n \le 10^{5}~, ~1 \le m \le 10^{9~});

n dòng tiếp theo: dòng thứ i gồm hai số nguyên dương c{i} và b{i} (1 ≤ c{i} ≤ 10^{6}, 1 ≤ b{i} ≤ 10^{6}).

Output

Một số nguyên duy nhất: số bạn nữ tối đa Hoàng có thể mua socola cho.

Giới hạn

~1 \le n \le 10^{5} 1~ ≤ ~m \le 10^{9} 1~ ≤ c_{i} ≤ 10^{6}

1 ≤ b_{i} ≤ 10^{6}

Sample Input

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

Sample Output

8