对齐刻度

吉数找完了，但Echo-0的数学迷宫里还有一个难题——刻度。不同的刻度，要对齐。

"刻度？"CC问。

"对。"你说，"给定$n$个同余方程，$x\equiv a_i\pmod{m_i}$。求$x$。"

"同余？"

"对。"你说，"$x$除以$m_i$的余数是$a_i$。"

"咋对齐？"

"中国剩余定理。"你说，"如果所有$m_i$两两互质，那么解唯一模$M=\prod m_i$。"

"不互质呢？"

"更复杂。"你说，"要两两合并，每次合并两个方程。"

"合并？"

"对。"你说，"$x\equiv a_1\pmod{m_1}$和$x\equiv a_2\pmod{m_2}$合并成一个方程。"

"咋合并？"

"用扩展欧几里得。"你说，"找$t$使得$a_1+m_1t\equiv a_2\pmod{m_2}$，然后新的模是$\text{lcm}(m_1,m_2)$。"

"第47个刻度。"你说，"$x\equiv 1\pmod{47}$——$x=48,95,142\dots$"

"好多。"

"对。"你说，"但如果再加一个条件，$x\equiv 2\pmod{3}$——答案就唯一模141。"

"141？"

"对。"你说，"$47\times 3=141$。"

"对齐了。"

"对。"你说，"对齐了。"

CC看着那些刻度线——像尺子，像时间轴，像某种命运的刻度。

"以前我的时间不对。"她说，"矿区的钟坏了，我一直不知道几点。"

"现在呢？"

"现在对了。"她说，"和你们在一起，时间对了。"

Echo把141存进记忆——不是作为数字，是作为某个瞬间的标记。

"141。"她说，"记住了。"

题目描述

给定$n$个同余方程$x\equiv a_i\pmod{m_i}$，求最小非负整数解。

输入格式

第一行$n$。接下来$n$行，每行$a_i$和$m_i$。

输出格式

最小非负整数解。无解输出$-1$。

输入样例

5

输出样例

0

提示

• 两两合并同余方程。
• 用扩展欧几里得求解$a_1+m_1t\equiv a_2\pmod{m_2}$。
• 新模为$\text{lcm}(m_1,m_2)$。