Đề 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 ≤ 10⁵, 1 ≤ m ≤ 10⁹);

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⁶, 1 ≤ b_i ≤ 10⁶).

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 ≤ n ≤ 10⁵

1 ≤ m ≤ 10⁹

1 ≤ c_i ≤ 10⁶

1 ≤ b_i ≤ 10⁶

Sample Input

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

Sample Output

8