No testdata at current.

题目描述

给定 $2n$ 个整数 $a_1,a_2,…,a_n$ 和 $m_1,m_2,…,m_n$，求一个最小的非负整数 $x$，满足

$∀i∈[1,n],x≡m_i(\mod a_i)$。

输入格式

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

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

输出格式

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

数据范围

$1≤a_i≤2^{31}−1$，

$0≤m_i<a_i$，

$1≤n≤25$

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

输入样例：

2
8 7
11 9

输出样例：

31