Арпа нашел список из n чисел. Он считает, что список плохой, если и только если он не пустой и НОД (см. примечания для пояснения) чисел в списке равен 1.
Арпа может выполнять следующие два типа операций:
- Выбрать число и удалить его, стоимость операции равна x,
- Выбрать число и увеличить его на 1, стоимость операции равна y.
У Арпы нет ограничений на количество применений второй операции на одно и то же число.
Помогите Арпе найти минимально возможную стоимость сделать список хорошим.
Выходные данные
Выведите одно число: минимальную стоимость сделать лист хорошим.
Примечание
В первом примере число 1 должно быть удалено (со стоимостью 23), а число 16 должно быть увеличено на 1 (со стоимостью 17).
НОД (наибольший общий делитель) множества чисел равняется максимальному целому числу, которое делит все числа из множества. Больше информации о НОД здесь.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 23 17
1 17 17 16
|
40
|
|
2
|
10 6 2
100 49 71 73 66 96 8 60 41 63
|
10
|