题目描述

自从朱最学搞定了 $\red Q$ 农场以后，就开始捉摸去 $\red Q$ 牧场干些事业，不仅在自己的牧场养牛，还到阿九的牧场放牛！

阿九很生气，有一次朱最学想知道阿九牧场奶牛的数量，于是阿九想狠狠耍朱最学一把。

举个例子，假如有 $\red{16}$ 头奶牛，如果建了 $\red 3$ 个牛棚，剩下 $\red 1$ 头牛就没有地方安家了。

如果建造了 $\red 5$ 个牛棚，但是仍然有 $\red 1$ 头牛没有地方去，然后如果建造了 $\red 7$ 个牛棚，还有 $\red 2$ 头没有地方去。

你作为阿九的私人秘书理所当然要将准确的奶牛数报给阿九，你该怎么办？

输入格式

第一行包含一个整数 $\red n$ 表示建立牛棚的次数。

接下来 $\red n$ 行，每行两个整数 $\red{a_i}$ ,$\red{b_i}$ , 表示建立了 $\red{a_i}$ 个牛棚，有 $\red{b_i}$ 头牛没有去处。

你可以假定不同 $\red{a_i}$ 之间互质。

输出格式

输出包含一个正整数，即为阿九至少养奶牛的数目。

样例

输入样例

3
3 1
5 1
7 2

输出样例

16

提示

$\red{1\leq n\leq 10}$,

$\red{1\leq a_i ,b_i\leq 1200000}$