eolymp
bolt
Try our new interface for solving problems
Problems

День изобилия

День изобилия

Time limit 1 second
Memory limit 64 MiB

В порт под названием Гренландия, находящийся на берегу Разноцветного Моря, иногда заходят корабли, которые привозят разнообразные товары, продающиеся затем в магазинах близлежащего поселка. Всего существует N кораблей и каждый из них заходит в этот порт с некоторой периодичностью.

Тяжела жизнь жителей поселка в дни, когда нет ни одного корабля - ведь мало того, что к магазину нужно пробираться через колючую проволоку и минные поля, рискуя упасть на них в канализационный люк, так еще и в самом магазине нечего будет купить. А выехать в более-менее цивилизованное место, где есть рынок или супермаркет, просто невозможно из-за непомерной дороговизны проезда в маршрутках, набиваемых поэтому селедкой, а не людьми.

Теперь вы легко можете представить себе как велика радость "гренладцев", когда в порт заходит хотя бы один корабль. Ведь тогда наконец-то в магазинах появятся хотя бы какие-нибудь продукты. Но вряд ли вы сможете даже представить себе ту радость, которую испытывают жители в такой день, когда в порт приходят все N кораблей. Этот день по праву считается днем изобилия.

Жители Гренландии слезно просят вас написать программу, которая определяла бы сколько им нужно ждать такого дня.

Input data

В первой строке входного файла задано количество кораблей N (1N100). В последующих N строках записаны по два натуральных числа – первый день, когда соответствующий корабль приходит в порт, и количество дней, через которое он будет снова появляться в нем каждый раз. Все числа не превосходят 10^9.

Output data

В единственную строку выходного файла необходимо вывести номер первого дня, в который в порту соберутся все корабли. В случае, если такого дня не существует, необходимо вывести число -1. Вы можете предполагать, что если такой день существует, то его номер не превышает 2·10^9.

Examples

Input example #1
3
4 5
3 4
1 6
Output example #1
19
Author Виталий Неспирный