题目描述

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

输入格式

第 1 行包含整数$n$。

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

输出格式

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

所有$m_i$ 的最小公倍数在 64 位有符号整数范围内。

样例

2
8 7
11 9

31

数据范围

• $1≤a_i≤2^{31}−1$
• $0≤m_i<a_i$
• $1≤n≤25$

来源

• POJ2891
• 算法竞赛进阶指南