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.
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 one integer: the number of positive integers that satisfy all the given constraints.
2 10 7 1 8 2
2
