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 < i_2 < \ldots < 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 $ .

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

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

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