题目描述

zx现在有$2n$个整数a~1~，a~2~，$…$ ，a~n~和m~1~，m~2~，$…$ ，m~n~，他想知道有没有一个最小的非负整数$x$满足∀ $i$ ∈[ $1,n$ ],$x ≡$ $m$~i~( $mod$ $a$~i~ )。你能帮他求出来吗？

输入格式

第1行包含整数$n$。

第2 到 $n+1$ 行$:$ 每$i + 1$ 行包含两个整数 $a$~i~ 和 $m$~i~ ，数之间用空格隔开。

输出格式

输出最小非负整数 $x$，如果 $x$ 不存在，则输出 $−1$。

输入样例

2
8 7
11 9

输出样例

31

提示

对于所有评测样例$:$

$1≤a$~i~$≤2$^31^$−1$,

$0≤m$~i~ $<a$~i~ $1≤n≤25$ 所有 $m$~i~ 的最小公倍数在 $64$ 位有符号整数范围内。