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