Кажется, Боря серьезно заболел. Чтобы проверить это и узнать точный диагноз, ему нужно пройти обследование у n врачей. Каждому из врачей требуется вся информация обо всех предыдущих обследованиях, поэтому Боря должен посещать их в заданном порядке (т. е. сначала посетить доктора 1, затем доктора 2, затем доктора 3 и так далее). И только от последнего врача Боря получит информацию о своём здоровье.
График работы у врачей непростой. Врач под номером i выходит на работу в день si и работает каждый di-й день. Таким образом, он работает в дни si, si + di, si + 2di, ....
Приём врача занимает довольно много времени, поэтому Боря не может посещать более чем одного врача за день. За какое наименьшее время он сможет обойти всех врачей?
Выходные данные
Выведите наименьший возможный номер дня, в который Боря может получить результат.
Примечание
В первом примере Боря может посетить врачей в дни 2, 3 и 4.
Во втором примере Боря может посетить врачей в дни 10 и 11.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 2
1 2
2 2
|
4
|
|
2
|
2
10 1
6 5
|
11
|