Có \(n\) robot, robot thứ \(i\) sẽ làm \(a_i\) sản phẩm mỗi ngày, nhưng phải nghỉ ngơi \(1\) ngày sau khi làm \(c_i\) ngày liên tiếp.

Yêu cầu: Tính số lượng ngày ít nhất để \(n\) robot làm ra \(m\) sản phẩm.

Input

• Dòng 1: chứa hai số guyên \(n,m (1≤n≤100,1≤m≤10^15 )\)

• Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa hai số nguyên \(a_i ,c_i (1≤a_i ,c_i≤10^{15} ).\)

Output

• Ghi ra một số duy nhất là số ngày ít nhất để \(n\) robot làm ra \(m\) sản phẩm.

Ràng buộc:

• Subtask 1: \(1≤n≤100,m,a_i,c_i≤10^4.\)

• Subtask 2: không có ràng buộc gì thêm.

Sample Input

2 30
2 5
1 9

Sample Output

11