Description

---

Elina is reading a book written by Rujia Liu, which introduces a strange way to express non-negative integers. The way is described as following:

Choose k different positive integers a1, a2, …, ak. For some non-negative m, divide it by every ai (1 ≤ i ≤ k) to find the remainder ri. If a1, a2, …, ak are properly chosen, m can be determined, then the pairs (ai, ri) can be used to express m.

“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.

Source

---

POJ Monthly--2006.07.30, Static

参考代码

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

#define REP(i,x,n) for(int i=x;i<=n;i++)

#define DEP(i,x,n) for(int i=n;i>=x;i--)

#define mem(a,x) memset(a,x,sizeof(a))

using namespace std;

ll read(){

    ll x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

void Out(ll a){

    if(a<0) putchar('-'),a=-a;

    if(a>=10) Out(a/10);

    putchar(a%10+'0');

}

const int N=1e6+10;

void exgcd(ll a,ll b,ll &d,ll &x,ll &y){

     if(b==0){

         x=1;y=0;

         d=a;

     }else{

         exgcd(b,a%b,d,y,x),y-=x*(a/b);

     }

}

int a[N],r[N],n;

ll solve(){

    ll ta=a[1],tr=r[1],x,y,d;

    for(int i=2;i<=n;i++){

        exgcd(ta,a[i],d,x,y);

        if((r[i]-tr)%d) return -1;

        x=(r[i]-tr)/d*x%(a[i]/d);

        tr+=x*ta;ta=ta/d*a[i];

        tr%=ta;

     }

     return tr>0?tr:tr+ta;

}

int main(){

    while(~scanf("%d",&n)){

        REP(i,1,n) a[i]=read(),r[i]=read();

        Out(solve());

        puts("");

    }

    return 0;

}