Problem Description

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.

Input

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

In each test case:

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

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

It's guarenteed that in all test cases, $ \sum n \le 50000 $

Output

For each test case:

You need to print a integers represents the smallest cost.

1
7 3
1 5 7 2 1 4 8

13