同余方程组的最小解

题目描述

给定 $n$ 对 $a_i,b_i$，请你求出最小的 $x$，使得 $x$ 满足 $x\bmod a_i \equiv b_i,i\in(1,n)$。

输入描述

第 $1$ 行为一个整数 $n$。

接下来的 $n$ 行每行包含两个整数 $a_i,b_i$。

$1\leq n\leq 10,0\leq b_i\leq a_i \leq 10^5$，保证对于任意的 $i,j$， $a_i,a_j$ 都互质。

输出描述

输出包含一个正整数，表示答案。

输入输出样例

示例 1

>输入

3
3 1
5 2
7 3

>输出

52