Так как Мансур устал делать легенды, легенды на эту задачу не будет.
Дан массив натуральных чисел \(a_1, a_2, \ldots, a_n\). В нём можно переставить элементы произвольным образом. Требуется узнать минимально возможное значение выражения \(\)\gcd(a_1) + \gcd(a_1, a_2) + \ldots + \gcd(a_1, a_2, \ldots, a_n),\(\) где \(\gcd(a_1, a_2, \ldots, a_n)\) обозначает наибольший общий делитель (НОД) чисел \(a_1, a_2, \ldots, a_n\).
Выходные данные
Для каждого набора входных данных выведите единственное число в отдельной строке — ответ на задачу.
Примечание
В первом наборе входных данных можно переставить элементы следующим образом: \([2, 4, 2]\), тогда ответом будет \(\gcd(2) + \gcd(2, 4) + \gcd(2, 4, 2) = 2 + 2 + 2 = 6\).
В третьем наборе входных данных можно переставить элементы следующим образом: \([6, 10, 15]\), тогда ответом будет \(\gcd(6) + \gcd(6, 10) + \gcd(6, 10, 15) = 6 + 2 + 1 = 9\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
4 2 2
2
6 3
3
10 15 6
5
6 42 12 52 20
4
42 154 231 66
|
6
6
9
14
51
|