【模板】扩展中国剩余定理（EXCRT）

题目描述

给定 $n$ 组非负整数 $a_i, b_i$ ，求解关于 $x$ 的方程组的最小非负整数解。

$$\begin{cases}x\equiv b_1\pmod{a_1}\\x\equiv b_2\pmod{a_2}\\\dots\\x\equiv b_n\pmod{a_n}\end{cases}$$

输入格式

输入第一行包含整数 $n$。

接下来 $n$ 行，每行两个非负整数 $a_i, b_i$。

输出格式

输出一行，为满足条件的最小非负整数 $x$。

输入样例 #1

3
11 6
25 9
33 17

输出样例 #1

809

输入样例 #2

2
3 0
5 0

输出样例 #2

0

输入样例 #3

2
3 1
5 2

输出样例 #3

7

数据范围

对于 $100 \%$ 的数据，$1 \le n \le {10}^5$，$1 \le a_i \le {10}^{12}$，$0\leq b_i \leq 10^{12}$，保证所有 $a_i$ 的最小公倍数不超过 ${10}^{18}$。