题目描述

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

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

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

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

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

输入格式

第一行包含一个整数 $n$ —— 建立牛棚的次数，接下来 $n$ 行，每行两个整数 $a_i, b_i$，表示建立了 $a_i$ 个牛棚，有 $b_i$ 头奶牛没有去处。你可以假定 $a_1 \sim a_n$ 互质。

输出格式

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

输入输出样例 #1

输入 #1

3
3 1
5 1
7 2

输出 #1

16

说明/提示

$1 \leq n\le10$，$0 \leq b_i\lt a_i\le100000$，$1 \leq \prod a_i \leq 10^{18}$