A. Monotonically Increasing Tardiness Informatics Tournament
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Check out Python input/output or C++ input/output or Java input/output for reading in the input numbers.

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 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 \lt 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
Note

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.