Klee likes to make friends,now there are $n$ people standing in a line and Klee can make friend with the $i$th people with a cost of $a_i$, Klee has a principle that at least $2$ out of $m$ consecutive people must be her friends. Please help her calculate the minimum amount of costs she needs.

The first line of the input contains a single integer $T(1≤T≤20)$indicating the number of test cases.

In each test case:

The first line contains two integers $n,m.(2≤n≤20000,2≤m≤2000,m≤n)$

The second line contains $n$ intergers $a_1,a_2,...,a_n(0≤a_i≤20000)$

It's guarenteed that in all test cases, $∑n≤50000$

For each test case:

You need to print a integers represents the smallest cost.