The organizing beavers of the Monotonically Increasing Tardiness Informatics Tournament (MITIT) need to meet regularly to ensure that the contest runs smoothly, but they sometimes lose motivation.

There are $N$ organizing beavers who regularly have meetings that last exactly $M$ minutes. The $i^{\text{th}}$ beaver shows up $t_i$ minutes late on the first meeting. On each successive meeting, beaver $i$ comes $a_i$ minutes later than they did to the previous meeting. Output the first meeting where everyone is so late that they all miss the entire meeting.

A beaver is said to have missed the entire meeting if they arrive \textbf{at least} $M$ minutes late.

Input

The first line contains two space-separated integers $N$ ($ 1 \le N \le 2\cdot 10^5$) and $M$ ($ 1 \le M \le 10^9$).

The $i^{\text{th}}$ of the next $N$ lines contains two integers $t_i$ ($0 \le t_i < M$) and $a_i$ ($1 \le a_i \le 10^9$).

Output

Output one line with the answer.

Example

Input

4 60
0 9
30 4
10 12
14 9

Output

9

Notes

For the first meeting, Beaver $1$ arrives on time, Beaver $2$ arrives $30$ minutes late, Beaver $3$ arrives $10$ minutes late, and Beaver $4$ arrives $14$ minutes late. For meeting $9$, Beaver $1$ arrives $72$ minutes late, Beaver $2$ arrives $62$ minutes late, Beaver $3$ arrives $106$ minutes late, and Beaver $4$ arrives $86$ minutes late. This is the first meeting for which everyone arrives at least $60$ minutes late; for meeting $8$, Beaver $2$ arrives $58$ minutes late.