给定 $2n$ 个整数 $a_1,a_2,…,a_n$ 和 $m_1,m_2,…,m_n$，求一个最小的非负整数 $x$，满足 $\forall i \in [1,n],x \equiv m_i(mod\ a_i)$。

输入格式

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

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

输出格式

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

数据范围

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

输入样例：

2
8 7
11 9

输出样例：

31