题目描述

小X和小J是同桌，也是最好的朋友。一天，他们在数学课上得到了一串数字——一个长度为 $n$ 的正整数数组 $a$，还有一个神秘的数字 $k$。

这是一个有趣的游戏，规则如下：首先，小X需要选择一个奇数 $x$（$1 \le x \le n$），这个 $x$ 将贯穿始终。然后，小J最多可以进行 $k$ 次操作（也可以一次都不做）。每次操作，小J可以挑选数组中的任意 $x$ 个位置（按顺序，但不必连续），构成一个子序列。接着，他会把这 $x$ 个数字全部替换成这个子序列的中位数。注意，中位数是指排序后中间的那个数，因为 $x$ 是奇数，所以中位数唯一。

小J很聪明，他想让整个数组的和变得尽可能大。而小X则负责先定下那个关键的 $x$。两人合作，试图找出经过最多 $k$ 次操作后，数组元素和的最大可能值。

他们开始思考：如果选的 $x$ 太小，每次操作改变的数字少，但中位数可能不大；如果选的 $x$ 太大，一次能改很多数，但中位数可能受限于数组的分布。而且每次操作后，数组会变化，后续操作要基于新数组。

他们拿起笔，在纸上画起了数组，尝试着模拟各种情况。比如，如果数组里有很大的数，也许可以通过操作让更多数变成大数？但中位数可能不是最大的那个，得小心。

故事就这样开始了，小X和小J要一起解开这个谜题，找到那个神奇的最大和。而你知道答案吗？

形式化题意

给定一个长度为 $n$ 的正整数数组 $a$ 和一个正整数 $k$：

• 选择一个奇数 $x$（$1 \le x \le n$）。
• 然后最多进行 $k$ 次操作（可以一次也不做）：
  • 选择一个长度为 $x$ 的 $a$ 的子序列，并将该子序列中的所有值替换为该子序列的中位数。具体地，选择 $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}])$， $\forall d$（$1 \le d \le x$）。

注意，你选择的奇数 $x$ 在所有操作中都不能更改。

请你最大化操作后 $a$ 的元素和。

输入格式

每个测试点包含多组测试用例。第一行为测试用例组数 $t$。每组测试用例的描述如下：

每组测试用例的第一行包含两个整数 $n$ 和 $k$，分别表示数组 $a$ 的长度和最多可执行操作次数。

第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le 10^9$）。

输出格式

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

输入输出样例

输入 #1

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

输出 #1

25
13
13
14
997420563
522
105

样例解释 #1

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

数据范围