310263: CF1806F2. GCD Master (hard version)

F2. GCD Master (hard version)time limit per test3 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

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.

Input

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

Output

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

ExampleInput

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

Output

11
14
1
18000000000000000000

Note

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

题目大意：
这是一个困难版本的题目，与简单版本唯一的不同是限制了整数$m$的取值。只有当两个版本的题目都被解决时，才能进行hack操作。给定一个长度为$n$的数组$a$以及两个整数$m$和$k$，数组中的每个元素满足$1 \le a_i \le m$。每次操作，你需要选择两个下标$i$和$j$满足$1 \le i < j \le |a|$，然后将$\gcd(a_i, a_j)$（即$a_i$和$a_j$的最大公约数）添加到数组末尾，并从数组中删除$a_i$和$a_j$。注意，每次操作后数组的长度会减少1。在进行了恰好$k$次操作后，求数组可能达到的最大和。

输入输出数据格式：
输入：
- 第一行包含一个整数$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$。

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

示例：
输入：
```
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
```

注意：
在第一个测试用例中，最佳操作是第一次操作选择$i=1$，$j=3$。最终序列是$[7,4]$。题目大意： 这是一个困难版本的题目，与简单版本唯一的不同是限制了整数$m$的取值。只有当两个版本的题目都被解决时，才能进行hack操作。给定一个长度为$n$的数组$a$以及两个整数$m$和$k$，数组中的每个元素满足$1 \le a_i \le m$。每次操作，你需要选择两个下标$i$和$j$满足$1 \le i < j \le |a|$，然后将$\gcd(a_i, a_j)$（即$a_i$和$a_j$的最大公约数）添加到数组末尾，并从数组中删除$a_i$和$a_j$。注意，每次操作后数组的长度会减少1。在进行了恰好$k$次操作后，求数组可能达到的最大和。 输入输出数据格式： 输入： - 第一行包含一个整数$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$。 输出： - 对于每个测试用例，输出进行$k$次操作后数组可能达到的最大和。 示例： 输入： ``` 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 ``` 注意： 在第一个测试用例中，最佳操作是第一次操作选择$i=1$，$j=3$。最终序列是$[7,4]$。