Sô-cô-la cho bò

Farmer John có \(B\) đô la để mua sô-cô-la cho những con bò của mình. Cửa hàng có \(N\) loại sô-cô-la, mỗi loại có số lượng không giới hạn.

• Loại sô-cô-la thứ \(i\) có giá \(P_i\) đô la.
• Có đúng \(C_i\) con bò chỉ thích loại sô-cô-la này.

Mỗi con bò chỉ được ăn một gói sô-cô-la. Farmer John muốn mua sô-cô-la để phục vụ càng nhiều bò càng tốt.

Với số tiền \(B\) và thông tin về \(N\) loại sô-cô-la, hãy tính số lượng bò tối đa mà Farmer John có thể phục vụ.

Input

Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(B\) (\(1 \le N \le 10^5\), \(1 \le B \le 10^{18}\)).
• \(N\) dòng tiếp theo, dòng thứ \(i+1\) chứa hai số nguyên dương \(P_i\) và \(C_i\) (\(1 \le P_i, C_i \le 10^{18}\)), lần lượt là giá và số lượng bò thích loại sô-cô-la thứ \(i\).

Output

In ra một số nguyên duy nhất là số bò tối đa có thể được phục vụ.

Example

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

8