CF1806F2.GCD Master (hard version)

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 \lt 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.

这是该问题的困难版本。两个版本的唯一区别在于对 $m$ 的约束条件。仅当两个版本的问题均被解决时，你才可以进行 hack。

给定一个长度为 $n$ 的数组 $a$ 以及两个整数 $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$。注意：执行该操作后，数组长度减少 $1$。

求恰好执行 $k$ 次操作后，数组元素之和的最大可能值。

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$.

第一行包含一个整数 $t$（$1\le t\le 10^5$）—— 表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$2 \le n \le 10^6$；$1\le m \le 9\cdot 10^{18}$；$1 \le k \le n-1$）。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le m$）。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

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

对于每个测试用例，输出执行 $k$ 次操作后数组可能达到的最大和。

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]$.

在第一个测试用例中，最优方案是在第一次操作中选择 $i=1$、$j=3$。最终序列为 $[7,4]$。