题目描述

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

输入格式

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

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

输出格式

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

样例

输入样例：

2
8 7
11 9

输出样例：

31

样例解释

我们需要找到一个 $x$，使得： [ \begin{cases} x \equiv 7 \pmod{8} \ x \equiv 9 \pmod{11} \end{cases} ] 检验 $x=31$：

• $31 \bmod 8 = 7$ ✅
• $31 \bmod 11 = 9$ ✅ 并且 $31$ 是满足条件的最小非负整数。

数据范围

• $1 \le n \le 25$
• $1 \le a_i \le 2^{31}-1$
• $0 \le m_i < a_i$
• 所有 $m_i$ 的最小公倍数在 64 位有符号整数范围内（注意：这里应为 $a_i$ 的最小公倍数在范围内）

时空限制

• 时间限制：1 秒
• 空间限制：64 MB