Migrated from Lutece 1403 咸鱼的跑步比赛

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

旅行到喵哈村的谭爷，发现一个超自然现象！

这里的咸鱼是跳着移动的！而且每次移动的距离相同，而且都是整数！！

突然，他有了强烈的好奇心，想知道咸鱼们能不能汇合到一起嘞？ 为了简化了问题，他强行将咸鱼们放在一条直（数）线（轴）上，并且将所在的位置强行规定成了在正半轴的整点！

amzing

先在给你此刻咸鱼的只数，其跳跃的距离ni，第i只咸鱼的位置ai，有没有合适的位置x让咸鱼们集合在一起。

（咸鱼可以向左也可以向右跳哟~）

如果没有输出-1

有的话找到并输出一个最小的符合条件的正整数x

谭爷仔细想了想，感觉暴力似乎是没法做的！

Input

第一行，咸鱼只数n

n<=100

第二到第n+1行有两个正整数表示ni 和 ai

1<=ni,ai<=1000

Output

一行，表示最小的符合条件的正整数x 可能很大！请用long long

Samples

2
8 7
11 9

31

Resources

2016 UESTC Training for Math