Description

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

Input Format

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

Output Format

输出最小非负整数$x$，如果$x$不存在，则输出−1。
如果存在$x$，则数据保证$x$一定在64位整数范围内。

2
8 7
11 9

31

Hint

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

Source

2.4数学知识 中国剩余定理