Klee likes making friends

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.

Sample Input

1
7 3
1 5 7 2 1 4 8

Sample Output

13

Source

2023“钉耙编程”中国大学生算法设计超级联赛（2）