CF2154E No Mind To Think

给定一个长度为 $n$ 的正整数数组 $a$ 和一个正整数 $k$，你将和它们进行如下的游戏： - 游戏开始时，你将选择一个奇数 $x$（$1 \le x \le n$）。 - 然后最多进行 $k$ 次如下操作（可以一次也不做）： - 选择一个长度为 $x$ 的 $a$ 的子序列，并将该子序列中的所有值替换为该子序列的中位数$^{\text{∗}}$。具体地，选择 $x$ 个整数 $i_1,\ldots,i_x$（$1 \le i_1 < i_2 < \ldots < i_x \le n$）。然后同时执行 $a_{i_d} := \mathrm{median}([a_{i_1},a_{i_2},\ldots,a_{i_x}])$，对于所有 $d$（$1 \le d \le x$）。 注意，你选择的整数 $x$ 在所有操作中都不能更改。 请你判断，经过游戏操作后，数组 $a$ 的元素和的最大可能值是多少。 $^{\text{∗}}$ 数组 $a$ 长度为 $n$ 的中位数（记作 $\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$。

每个测试点包含多组测试用例。第一行为测试用例组数 $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$。

对于每组测试用例，输出一个整数，表示经过游戏操作后，数组 $a$ 的最大可能和。

在第一个测试用例中，一种得到 $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]$ 由 ChatGPT 5 翻译