A business received a big order for \(M\) products, they must deliver as soon as possible but there is nothing left in the
warehouse, they have to produce from scratch. They have \(N\) workers, worker \(i\) produce \(A_i\) products every day but take
\(1\) day of leave after every \(B_i\) days of work. Calculate what’s the earliest day they can finish producing \(M\) products to
deliver.

Input

• The first line of input contains 2 integers \(N\) and \(M\) \((1 \le N \le 100, 1 \le M \le 10^{15})\), the number of workers and
  number of products ordered.
• The next \(N\) lines, each has 2 numbers \(A_i\) and \(B_i (1 \le A_i, B_i \le 10^{15})\).

Output

• Output one integer, the number of days it take.

Example

2 30
2 5
1 9

11