题目描述

给定 $\red{2n}$ 个整数$\red{a_1}$,$\red{a_2}$,$\red{…}$,$\red{a_n}$和$\red{m_1}$ ,$\red{m_2}$ ,$\red{…}$,$\red{m_n}$ ,求一个最小的非负整数 $\red x$，满足 $\red{\forall i∈[1,n],x\equiv m_i \pmod {a_i}}$。

输入格式

第 $\red 1$ 行包含整数 $\red n$。

第 $\red{2...n}$ 行：每 $\red{i+1}$ 行包含两个整数 $\red{a_i}$ 和 $\red{m_i}$ , 数之间用空格隔开。

输出格式

输出最小非负整数 $\red x$，如果 $\red x$ 不存在，则输出$\red{-1}$。 如果存在 $\red x$，则数据保证 $\red x$ 一定在 $\red{64}$ 位整数范围内。

样例

输入样例

2
8 7
11 9

输出样例

31

提示

$\red{1\leq a_i \leq 2^{31} −1}$,

$\red{0\leq m_i<a_i}$,

$\red{1\leq n\leq 25}$