Migrated from Lutece 3031 上帝爱造人

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

今天，上帝又造了114514个人。 上帝忘记了从什么时候开始造人，忘记了每天造了多少人。但是看着空虚的大地，上帝还是觉得人不够多。 上帝已经不想再自己造人了，他决定让人们自食其力，因此上帝打算先将人们分组。 可是分组也不是一件简单的事。按照相同的人数分为一组，最后可能还会剩下一些人没办法分成一组。所以上帝打算先统计人数。

Input

第一行一个整数$n$，表示分组的情况。 接下来$n$行，第$i$行两个整数$a_i,b_i$，表示$a_i$个人一组后还剩下$b_i$个人没分组。保证$a_i$为质数。

Output

一行一个正整数，表示上帝最少造了多少个人。

Samples

3
3 1
5 1
7 2

16

Constraints

$1\leq n\leq 10,0\leq b_i<a_i\leq 10^5$, $1\leq \prod a_i\leq10^{18}$.

Note

16个人分成3组，还剩1个人；分成5组，还剩1个人；分成7组，还剩2个人。

Resources

2023 UESTC ICPC Training for Math