H. Hide and Seek
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Eva is playing a special game of "hide and seek" with Colin. Unlike the traditional game, Eva chooses a hidden positive integer $$$x$$$ for Colin to guess.

First, Eva tells Colin a positive integer $$$a$$$ and guarantees that $$$x\le a$$$.

Then Eva gives Colin $$$m$$$ constraints. Constraint $$$j$$$ consists of two non-negative integers $$$b_j$$$ and $$$c_j$$$ and requires $$$$$$ b_j\bmod x=c_j. $$$$$$

Colin wants to enumerate every possible value of $$$x$$$, but he does not know how many there are. Determine the number of positive integers $$$x\le a$$$ that satisfy all the constraints.

It is guaranteed that at least one such integer exists.

Input

The first line contains two integers $$$m$$$ and $$$a$$$ ($$$1\le m\le 2\times 10^5$$$, $$$1\le a\le 10^9$$$), the number of constraints and the upper bound on $$$x$$$, respectively.

Each of the next $$$m$$$ lines contains two integers $$$b_j$$$ and $$$c_j$$$ ($$$0\le c_j\le b_j\le 10^9$$$), describing the constraint $$$b_j\bmod x=c_j$$$.

Output

Output one integer: the number of positive integers that satisfy all the given constraints.

Example
Input
2 10
7 1
8 2
Output
2