GCD Master (hard version)

给定 $n, m$ 和一个长度为 $n$ 的序列 $\{a_i\} (a_i\leq m)$。 定义一次对一个长度为 $m$ 的序列的操作为，选择序列中两个下标 $1\leq i < j \leq m$，删去 $a_i$ 与 $a_j$，然后在序列末端加入 $\gcd(a_i, a_j)$。 例如，对于 $[7, 6, 2]$，一次操作可以选择下标 $2$ 与 $3$，这样操作后，序列变成 $[7, 2]$。 给定 $k$，求对序列 $\{a_i\}$ 执行 $k$ 次操作后得到序列中的数的和的最大值。

This is the hard version of the problem. The only difference between the two versions is the constraint on $ m $ . You can make hacks only if both versions of the problem are solved. You are given an array $ a $ of length $ n $ and two integers $ m $ and $ k $ . Each element in $ a $ satisfies $ 1\le a_i \le m $ . In one operation, you choose two indices $ i $ and $ j $ such that $ 1 \le i < j \le |a| $ , then append $ \gcd(a_i,a_j) $ to the back of the array and delete $ a_i $ and $ a_j $ from the array. Note that the length of the array decreases by one after this operation. Find the maximum possible sum of the array after performing exactly $ k $ operations.

The first line contains a single integer $ t $ ( $ 1\le t\le 10^5 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains three integers $ n $ , $ m $ and $ k $ ( $ 2 \le n \le 10^6 $ ; $ 1\le m \le 9\cdot 10^{18} $ ; $ 1 \le k \le n-1 $ ). The second line of each test case contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 1 \le a_i \le m $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^6 $ .

For each test case, output the maximum possible sum of the array after performing $ k $ operations optimally.

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

In the first test case, the best way is to choose $ i=1 $ , $ j=3 $ in the first operation. The final sequence is $ [7,4] $ .