Nam sở hữu một khu vườn có trồng \(n\) cây, cây thứ \(i\) có độ tươi tốt hiện tại \(a_i\) và khả năng tăng trưởng \(b_i\). Hôm nay, Nam dự định sử dụng tổng cộng \(L\) lít nước để tưới cho các cây trong vườn. Với mỗi lít nước tưới vào một cây thứ \(i\), độ tươi tốt của cây sẽ tăng thêm \(b_i\). Ngoài ra, số lít nước tưới vào mỗi cây phải là số nguyên.

Nam đánh giá vẻ đẹp của khu vườn là độ tươi tốt bé nhất trong số n cây trong vườn. Hãy giúp Nam tìm cách tưới nước sao cho vẻ đẹp của khu vườn là lớn nhất có thể.

Dữ liệu

• Dòng thứ nhất ghi hai số nguyên \(n, L (1 ≤ n ≤ 10^5, 1 ≤ L ≤ 10^9)\) – số cây trong vườn và số lít nước dùng để tưới cây.

• n dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên \(a_i\) và \(b_i (1 ≤ a_i, b_i ≤ 10^4)\) - độ tươi tốt và khả năng tăng trưởng của cây thứ \(i\).

Kết quả

In ra vẻ đẹp lớn nhất có thể của khu vườn với cách tưới cây tối ưu.

Sample Input

3 5
1 5 
6 2 
3 3

Sample Output

8