2925. 表达整数的奇怪方式
时间限制：1000 MS 内存限制：128 MB
题目描述
# 表达整数的奇怪方式 ## 题目描述 给定 $2n$ 个整数 $a_1,a_2,\dots,a_n$ 和 $m_1,m_2,\dots,m_n$，求最小的非负整数 $x$，使得对于所有 $1\le i\le n$，均有 $$ x\equiv m_i\pmod{a_i}. $$ 也就是说，$x$ 除以 $a_i$ 的余数为 $m_i$。 如果不存在满足条件的非负整数，输出 $-1$。 ## 输入格式 从文件 `remains.in` 中读入数据。 第一行包含一个整数 $n$。 接下来 $n$ 行，第 $i$ 行包含两个整数 $a_i$ 和 $m_i$，以空格分隔。 ## 输出格式 将结果输出到文件 `remains.out` 中。 输出一行，包含一个整数，表示满足条件的最小非负整数 $x$；如果无解，则输出 $-1$。 ## 数据范围 - $1\le n\le 25$。 - $1\le a_i\le 2^{31}-1$。 - $0\le m_i<a_i$。 - 若有解，保证最小非负解在 $64$ 位整数范围内。 ## 样例输入 ``` 2 8 7 11 9 ``` ## 样例输出 ``` 31 ```