Джо нужны деньги. Его друг Чендлер хотел бы дать Джо их, но не может сделать это в открытую, так как Джо слишком гордый. А потому Чендлер решил схитрить и предложил Джо сыграть в игру.
В этой игре Чендлер задает Джо массив \(a_1, a_2, \dots, a_n\) (\(n \geq 2\)) из положительных целых чисел (\(a_i \ge 1\)).
Джо может применять к заданному массиву следующую операцию произвольное количество раз:
- Выбери две позиции \(i\) и \(j\) (\(1 \le i < j \le n)\).
- Выбери два целых числа \(x\) и \(y\) (\(x, y \ge 1\)) таких, что \(x \cdot y = a_i \cdot a_j\).
- Замени \(a_i\) на \(x\) и \(a_j\) на \(y\).
В конце Джо получит количество денег, равное сумме элементов массива.
Определите наибольшее количество денег \(\mathrm{ans}\), которое он может получить, но выведите \(2022 \cdot \mathrm{ans}\). Почему ответ, умноженный на \(2022\)? Потому что мы больше никогда его не увидим!
Гарантируется, что произведение всех чисел заданного массива \(a\) не превосходит \(10^{12}\).
Выходные данные
Для каждого набора данных выведите максимальное количество денег, которое может получить Джо, умноженное на \(2022\).
Примечание
В первом наборе входных данных Джо может проделать следующие операции:
- Он выбирает \(i = 1\) и \(j = 2\) (получая произведение \(a[i] \cdot a[j] = 6\)), выбирает \(x = 6\) и \(y = 1\) и присваивает \(a[i] = 6\) и \(a[j] = 1\). \(\)[2, 3, 2] \xrightarrow[x = 6,\; y = 1]{i = 1,\; j = 2} [6, 1, 2]\(\)
- Он выбирает \(i = 1\) и \(j = 3\) (получая произведение \(a[i] \cdot a[j] = 12\)), выбирает \(x = 12\) и \(y = 1\) и присваивает \(a[i] = 12\) и \(a[j] = 1\). \(\)[6, 1, 2] \xrightarrow[x = 12,\; y = 1]{i = 1,\; j = 3} [12, 1, 1]\(\)
Сумма станет равна
\(14\) и будет максимально возможной. Ответ же равен
\(2022 \cdot 14 = 28308\).