CF1440B Sum of Medians

A median of an array of integers of length $ n $ is the number standing on the $ \lceil {\frac{n}{2}} \rceil $ (rounding up) position in the non-decreasing ordering of its elements. Positions are numbered starting with $ 1 $ . For example, a median of the array $ [2, 6, 4, 1, 3, 5] $ is equal to $ 3 $ . There exist some other definitions of the median, but in this problem, we will use the described one. Given two integers $ n $ and $ k $ and non-decreasing array of $ nk $ integers. Divide all numbers into $ k $ arrays of size $ n $ , such that each number belongs to exactly one array. You want the sum of medians of all $ k $ arrays to be the maximum possible. Find this maximum possible sum.

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 100 $ ) — the number of test cases. The next $ 2t $ lines contain descriptions of test cases. The first line of the description of each test case contains two integers $ n $ , $ k $ ( $ 1 \leq n, k \leq 1000 $ ). The second line of the description of each test case contains $ nk $ integers $ a_1, a_2, \ldots, a_{nk} $ ( $ 0 \leq a_i \leq 10^9 $ ) — given array. It is guaranteed that the array is non-decreasing: $ a_1 \leq a_2 \leq \ldots \leq a_{nk} $ . It is guaranteed that the sum of $ nk $ for all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case print a single integer — the maximum possible sum of medians of all $ k $ arrays.

The examples of possible divisions into arrays for all test cases of the first test: Test case $ 1 $ : $ [0, 24], [34, 58], [62, 64], [69, 78] $ . The medians are $ 0, 34, 62, 69 $ . Their sum is $ 165 $ . Test case $ 2 $ : $ [27, 61], [81, 91] $ . The medians are $ 27, 81 $ . Their sum is $ 108 $ . Test case $ 3 $ : $ [2, 91, 92, 95], [4, 36, 53, 82], [16, 18, 21, 27] $ . The medians are $ 91, 36, 18 $ . Their sum is $ 145 $ . Test case $ 4 $ : $ [3, 33, 35], [11, 94, 99], [12, 38, 67], [22, 69, 71] $ . The medians are $ 33, 94, 38, 69 $ . Their sum is $ 234 $ . Test case $ 5 $ : $ [11, 41] $ . The median is $ 11 $ . The sum of the only median is $ 11 $ . Test case $ 6 $ : $ [1, 1, 1], [1, 1, 1], [1, 1, 1] $ . The medians are $ 1, 1, 1 $ . Their sum is $ 3 $ .