Кажется, Боря серьезно заболел. Чтобы проверить это и узнать точный диагноз, ему нужно пройти обследование у n врачей. Каждому из врачей требуется вся информация обо всех предыдущих обследованиях, поэтому Боря должен посещать их в заданном порядке (т. е. сначала посетить доктора 1, затем доктора 2, затем доктора 3 и так далее). И только от последнего врача Боря получит информацию о своём здоровье.

График работы у врачей непростой. Врач под номером i выходит на работу в день s_i и работает каждый d_i-й день. Таким образом, он работает в дни s_i, s_i + d_i, s_i + 2d_i, ....

Приём врача занимает довольно много времени, поэтому Боря не может посещать более чем одного врача за день. За какое наименьшее время он сможет обойти всех врачей?