Eva は Colin と特別な「かくれんぼ」をしています。普通のゲームとは異なり、Eva は隠された正整数 $x$ を選び、Colin に当ててもらいます。

まず Eva は Colin に正整数 $a$ を伝え、$x\le a$ であることを保証します。

その後、Eva は Colin に $m$ 個の条件を与えます。条件 $j$ は二つの非負整数 $b_j$ と $c_j$ からなり、次を要求します:

$$ b_j\bmod x=c_j. $$

Colin は $x$ の可能な値をすべて列挙したいのですが、その個数を知りません。すべての条件を満たす正整数 $x\le a$ の個数を求めてください。

そのような整数が少なくとも一つ存在することが保証されます。

入力

最初の行には二つの整数 $m$ と $a$ ($1\le m\le 2\times 10^5,1\le a\le 10^9$) が含まれ、それぞれ条件の数と $x$ の上限を表します。

続く $m$ 行にはそれぞれ二つの整数 $b_j$ と $c_j$ ($0\le c_j\le b_j\le 10^9$) が含まれ、条件 $b_j\bmod x=c_j$ を表します。

出力

与えられたすべての条件を満たす正整数の個数を、一つの整数として出力してください。

入出力例

入力 1

2 10
7 1
8 2

出力 1

2