Племя Чая считает, что существует \(n\) знамений апокалипсиса. Со временем выяснилось, что \(i\)-е знамение происходит каждые \(a_i\) лет (в года \(a_i\), \(2 \cdot a_i\), \(3 \cdot a_i\), \(\dots\)).
Согласно преданиям, чтобы наступил апокалипсис, знамения должны произойти последовательно. То есть сначала они дожидаются, когда впервые произойдёт первое знамение, потом строго после него произойдёт второе и так далее. То есть, если \(i\)-е знамение произошло в год \(x\), то племя начинает ждать наступления \((i+1)\)-го, начиная с года \(x+1\).
В каком году произойдёт \(n\)-е знамение и наступит апокалипсис?
Выходные данные
Для каждого набора входных данных выведите одно целое число — год, в котором произойдут все \(n\) знамений.
Примечание
В первом наборе входных данных примера:
- Племя дождётся первого знамения в \(3\) году;
- племя дождётся второго знамения в \(4\) году (так как \(2\) год уже прошёл);
- племя дождётся третьего знамения в \(8\) году (так как в \(4\) году уже произошло второе знамение);
- племя дождётся четвёртого знамения в \(10\) году (так как \(5\) год уже прошёл);
- племя дождётся пятого знамения в \(18\) году (так как \(9\) год уже прошёл);
- племя дождётся шестого знамения в \(36\) году (так как в \(18\) году уже произошло пятое знамение).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
6
3 2 4 5 9 18
5
1 2 3 4 5
5
1 1 1 1 1
6
50 30 711 200 503 1006
|
36
5
5
2012
|