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