题目大意：一个数字，除以a1余数为b1，除以a2余数为b2……除以an余数为bn，这个数存在吗？如果存在最小的是多少？
Description
“It is easy to calculate the pairs from m, ” said Elina. “But how can I find m from the pairs?”
Since Elina is new to programming, this problem is too difficult for her. Can you help her?
Input
The input contains multiple test cases. Each test cases consists of some lines.
- Line 1: Contains the integer k.
- Lines 2 ~ k + 1: Each contains a pair of integers ai, ri (1 ≤ i ≤ k).
Output
Output the non-negative integer m on a separate line for each test case. If there are multiple possible values, output the smallest one. If there are no possible values, output -1.
Sample Input
2 8 7 11 9
Sample Output
31
Hint
All integers in the input and the output are non-negative and can be represented by 64-bit integral types.
解题思路
模数不互质，不能直接用中国剩余定理。一个数%15=4，那么他%3=1，%5=4；如果他%3=1，%5=4，一定是%15=4吗？
设这个数为X，X = 3x+1 = 5y+4，3x – 5y = 3，一组解为x = 1，y = 0，代回去可得到X = 4。数字4就满足要求，增加lcm(3, 5)=15的倍数都满足要求，4是最小的，即两个条件可以转换成%15=4。
又如一个数%4=3，%6=5，可以是11，那么增加lcm(4, 6)=12也是满足要求的，可以转化成%12=11！
设这个数为X，X = 3x+1 = 5y+4，3x – 5y = 3，一组解为x = 1，y = 0，代回去可得到X = 4。数字4就满足要求，增加lcm(3, 5)=15的倍数都满足要求，4是最小的，即两个条件可以转换成%15=4。
接下来的问题是，ax + by = c是否有解？什么时候无解呢？裴蜀定理告诉我们，有解的充要条件是c是gcd(a, b)的整数倍，不是整数倍即无解。
再接下来的问题就是如何解这个方程？扩展欧几里得算法！ax – by = c能算出来吗？算出来ax + by = c后将y取相反数就行？其实我们也可以让等式变得好看一点：X = -3x + 1 = 5y + 4，这样就可以得到3x + 5y = -3的式子，最终x*d + 0*0 = c即x=c/d回代，解得x=-1, y=0。
由于题目没有说n是多大，不方便开数组，故采取边读入边处理的形式。先读入第一组数据，作为起始的模数p和余数q，接下来每读入一组模数a和模数b，设X = -px+q = ay+b，即px + ay = q – b，若c = q-b不是gcd(p, a)的整数倍则无解，无解也不能马上退出循环，因为该组数据还没读完。有解则用求出来的x代入求出X（在q的基础上，减去px），需要注意的是，p*x可能会很大，x可以先%a，因为q减去p的整数倍，所以%p还是q，因为x%a后，去掉的也是a的整数倍，所以%a还是b，不影响结果的同时避免爆long long。
程序实现
