E. No Mind To Think
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array of positive integers $$$a$$$ of length $$$n$$$ and a positive integer $$$k$$$, and you will play the following game with them:

  • At the start of the game, you will choose an odd integer $$$x$$$ ($$$1 \le x \le n$$$).
  • Then do the following at most $$$k$$$ times (possibly none):
    • Select a subsequence of $$$a$$$ of length $$$x$$$, then replace every value in the subsequence with the median$$$^{\text{∗}}$$$ of that subsequence. More formally, pick $$$x$$$ integers $$$i_1,\ldots,i_x$$$ ($$$1 \le i_1 \lt i_2 \lt \ldots \lt i_x \le n$$$). Then simultaneously do $$$a_{i_d}$$$:= $$$\mathrm{median}([a_{i_1},a_{i_2},\ldots,a_{i_x}])$$$ for all $$$d$$$ ($$$1 \le d \le x$$$).

Note that the integer $$$x$$$ you choose cannot change between operations.

Determine the maximum value for the sum of $$$a$$$ obtainable after playing the game.

$$$^{\text{∗}}$$$The median of an array $$$a$$$ of length $$$n$$$ (written $$$\mathrm{median}(a)$$$) is the $$$\left\lfloor\frac{n + 1}{2}\right\rfloor$$$-th smallest element in $$$a$$$, where $$$\left\lfloor x \right\rfloor$$$ denotes the largest integer which is smaller than or equal to $$$x$$$. For example, $$$\mathrm{median}([4, 3, 1, 2, 5]) = 3$$$ and $$$\mathrm{median}([4, 3, 5, 3]) = 3$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains integers $$$n$$$ and $$$k$$$ ($$$3 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$, and the maximum number of times you can perform the operation.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$).

The sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output the maximum sum of $$$a$$$ achievable after playing the game.

Example
Input
7
5 1
1 1 5 5 5
3 1
10 1 2
6 3
1 1 2 3 1 2
5 1
1 2 2 3 5
3 1
332473521 409066963 155613323
6 6
81 71 90 15 87 36
7 2
4 13 11 19 15 16 10
Output
25
13
13
14
997420563
522
105
Note

A way to achieve $$$25$$$ in the first test case is to select $$$x = 5$$$ and then do:

  • $$$[\color{red}1, \color{red}1, \color{red}5, \color{red}5, \color{red}5] \rightarrow [5, 5, 5, 5, 5]$$$

A way to achieve $$$13$$$ in the third test case is to pick $$$x = 3$$$ and then do:

  • $$$[\color{red}1, 1, \color{red}2, 3, 1, \color{red}2] \rightarrow [\color{red}2, 1, \color{red}2, 3, \color{red}1, 2] \rightarrow [2, \color{red}1, \color{red}2, 3, \color{red}2, 2] \rightarrow [2, 2, 2, 3, 2, 2]$$$