CF2154E.No Mind To Think

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

给你一个长度为 $n$ 的正整数数组 $a$ 和一个正整数 $k$，你将与它们进行如下游戏：

• 游戏开始时，你需要选择一个奇数 $x$（满足 $1 \le x \le n$）。
• 然后最多执行 $k$ 次（也可不执行）以下操作：
  • 从 $a$ 中选出一个长度为 $x$ 的子序列，并将该子序列中每个值都替换为该子序列的中位数$^{\text{∗}}$。更准确地说，选取 $x$ 个下标 $i_1,\ldots,i_x$（满足 $1 \le i_1 \lt i_2 \lt \ldots \lt i_x \le n$），然后对所有 $d$（$1 \le d \le x$）同时令 $a_{i_d} := \mathrm{median}([a_{i_1},a_{i_2},\ldots,a_{i_x}])$。

注意：你在整个过程中选定的 $x$ 值不能更改。

求游戏结束后数组 $a$ 元素之和所能达到的最大值。

$^{\text{∗}}$ 长度为 $n$ 的数组 $a$ 的中位数（记作 $\mathrm{median}(a)$）定义为 $a$ 中第 $\left\lfloor\frac{n + 1}{2}\right\rfloor$ 小的元素，其中 $\left\lfloor x \right\rfloor$ 表示不超过 $x$ 的最大整数。例如，$\mathrm{median}([4, 3, 1, 2, 5]) = 3$，而 $\mathrm{median}([4, 3, 5, 3]) = 3$。

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$3 \le n \le 2 \cdot 10^5$，$1 \le k \le 2 \cdot 10^5$）——分别表示数组 $a$ 的长度以及你最多可执行操作的次数。

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

所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

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

对于每个测试用例，输出游戏结束后所能达到的 $a$ 的最大和。

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

第一组测试数据中得到 $25$ 的一种方法是选择 $x = 5$，然后执行以下操作：

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

第三组测试数据中得到 $13$ 的一种方法是选择 $x = 3$，然后执行以下操作：

• $[\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]$