Задача G. Делимая последовательность

Автор:Иван Кобец, Михаил Бадерик   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

Дана последовательность a = [a1, a2, …, an], состоящая из n положительных целых чисел.

Требуется удалить несколько (возможно, ноль) чисел из последовательности таким образом, чтобы:

  1. Наибольший общий делитель (НОД) всех чисел оставшихся чисел последовательности был больше 1.
  2. Сумма удалённых чисел была минимально возможной.

Формат входных данных

В первой строке задано одно натуральное число n — количество чисел в последовательности.

Во второй строке задано n натуральных чисел ai.

Формат выходных данных

Выведите минимально возможную сумму удаляемых чисел.

Ограничения

1 ≤ n ≤ 2 ⋅ 104

1 ≤ ai ≤ 104

Примеры тестов

Стандартный вход Стандартный выход
1
5
3 5 19 18 21
24
2
4
1 2 4 9
7
3
5
3 6 12 24 30
0

0.095s 0.015s 15