Strange Way to Express Integers
Description
给定2n个正整数 a1,a2,...,an 和 r1,r2,...,rn,求一个最小的正整数 x,满足∀ i∈[1,n],x≡ai(mod ri),或者给出无解。
Format
Input
多组数据。
每组数据第一行一个整数k。
接下来k行,每行两个整数 ai,ri。
Output
对于每组数据,若无解,输出“-1”;否则,输出一个非负整数,若有多解,输出最小的满足条件的答案。
Sample 1
Input
2
8 7
11 9
Output
31
Limitation
1s,128MiB for each test case.
Source
poj2891