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

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 2 ⋅ 10⁴

1 ≤ a_i ≤ 10⁴

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

5
3 5 19 18 21

24

4
1 2 4 9

7

5
3 6 12 24 30

0