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