问题描述

Elina 正在阅读刘汝佳的一本书，书中介绍了一种表示非负整数的独特方法。该方法描述如下：

选择 $k$ 个不同的正整数 $a_1, a_2, \dots, a_k$。对于某个非负整数 $m$，分别用每个 $a_i$（$1 \leq i \leq k$）去除 $m$，得到余数 $r_i$。如果 $a_1, a_2, \dots, a_k$ 选择得当，那么 $m$ 就可以被唯一确定，此时数对 $(a_i, r_i)$ 就可以用来表示 $m$。

"从 $m$ 计算出这些数对很容易，" Elina 说，"但我怎么从这些数对反推 $m$ 呢？"

由于 Elina 是编程新手，这个问题对她来说太难了。你能帮帮她吗？

输入格式

输入包含多个测试用例。每个测试用例由若干行组成：

• 第 1 行：包含整数 $k$。
• 第 2 ~ $k+1$ 行：每行包含两个整数 $a_i$ 和 $r_i$（$1 \leq i \leq k$）。

输出格式

对于每个测试用例，在单独的一行中输出非负整数 $m$。如果存在多个可能的 $m$ 值，输出最小的那个。如果没有可能的 $m$ 值，则输出 $-1$。

输入样例

2
8 7
11 9

输出样例

31

样例解释

对于样例输入：

• $k = 2$
• 第一个数对：$a_1 = 8$, $r_1 = 7$
• 第二个数对：$a_2 = 11$, $r_2 = 9$

我们需要找到一个非负整数 $m$，使得：

$$\begin{cases} m \equiv 7 \pmod{8} \\ m \equiv 9 \pmod{11} \end{cases} $$

验证：$31 \div 8 = 3 \cdots 7$，$31 \div 11 = 2 \cdots 9$，满足条件。且 $31$ 是该同余方程组的最小非负整数解。

数据范围与提示

• 输入和输出中的所有整数都是非负的。
• 所有整数都可以用 64 位整型（即 C++ 中的 long long 类型）表示。
• 题目来源：POJ Monthly--2006.07.30, Static