B. Sum of Medians
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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

Output

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

Example
Input
6
2 4
0 24 34 58 62 64 69 78
2 2
27 61 81 91
4 3
2 4 16 18 21 27 36 53 82 91 92 95
3 4
3 11 12 22 33 35 38 67 69 71 94 99
2 1
11 41
3 3
1 1 1 1 1 1 1 1 1
Output
165
108
145
234
11
3
Note

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