Это сложная версия задачи. Различия между версиями заключаются в ограничениях на \(m\). Вы можете делать взломы, только если обе версии задачи сданы.
Вам дан массив \(a\) длины \(n\) и два целых числа \(m\) и \(k\). Каждый элемент в \(a\) удовлетворяет условию \(1\le a_i \le m\).
За одну операцию вы выбираете два индекса \(i\) и \(j\) такие, что \(1 \le i < j \le |a|\), затем добавляете \(\gcd(a_i,a_j)\) в конец массива и удаляете \(a_i\) и \(a_j\) из массива. Обратите внимание, что после этой операции длина массива уменьшится на единицу.
Найдите максимально возможную сумму массива после выполнения ровно \(k\) операций.
Выходные данные
Для каждого набора входных данных выведите максимально возможную сумму массива после оптимального выполнения \(k\) операций.
Примечание
В первом наборе входных данных лучшим способом является выбор \(i=1\), \(j=3\) в первой операции. Итоговая последовательность — \([7,4]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 8 1
4 7 8
5 114514 2
7 2 4 1 6
3 1919810 2
2 3 3
3 9000000000000000000 1
9000000000000000000 9000000000000000000 9000000000000000000
|
11
14
1
18000000000000000000
|