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ᵢ tiền và có đúng bᵢ 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ᵢ và bᵢ (1 ≤ cᵢ ≤ 10⁶, 1 ≤ bᵢ ≤ 10⁶).

Output:

Một số nguyên duy nhất: số bò tối đa Hoàng có thể phục vụ.

Giới hạn

1 ≤ n ≤ 10⁵

1 ≤ m ≤ 10⁹

1 ≤ cᵢ ≤ 10⁶

1 ≤ bᵢ ≤ 10⁶

Sample Input

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

Sample Output

8