Лиса Сиель играет с числами.
У Сиель есть n положительных целых чисел: x1, x2, ..., xn. Она может выполнять следующие операции столько раз, сколько ей нужно: выбрать два различных индекса i и j, таких, что выполняется условие xi > xj, а затем выполнить присвоение xi = xi - xj. Цель игры в том, чтобы сделать сумму всех чисел как можно меньше.
Пожалуйста, помогите Сиель найти эту минимальную сумму.
Выходные данные
Выведите единственное целое число — требуемую минимальную сумму.
Примечание
В первом примере оптимальный способ — выполнить присвоение: x2 = x2 - x1.
Во втором примере оптимальная последовательность операций такая: x3 = x3 - x2, x2 = x2 - x1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 2
|
2
|
|
2
|
3
2 4 6
|
6
|
|
3
|
2
12 18
|
12
|
|
4
|
5
45 12 27 30 18
|
15
|