给定 2n 个整数 $a_1,a_2,…,a_n 和 m_1,m_2,…,m_n$，求一个最小的非负整数 x，满足

$∀i∈[1,n],x≡m_i(mod a_i)。$

输入格式

第 $1$行包含整数 $n$。

第 $2…n+1$ 行：第 $i+1$ 行包含两个整数$a_i 和 m_i$，数之间用空格隔开。

输出格式

输出最小非负整数 $x$，如果$x$ 不存在，则输出 −1。

数据范围

$1≤a_i≤2^{31}−1,$
$0≤m_i<a_i$ $1≤n≤25$ 所有 mi 的最小公倍数在 64 位有符号整数范围内。

输入样例：

2
8 7
11 9

输出样例：

31