题目描述

可莉喜欢交朋友。现在有 $n$ 个人站成一排，可莉可以与第 $i$ 个人交朋友，花费为 $a_i$。可莉有一个原则：在任意连续的 $m$ 个人中，至少有 $2$ 个人必须是她的朋友。请帮她计算出满足此条件所需的最小总花费。

输入格式

输入的第一行包含一个整数 $T$ ($1 \leq T \leq 20$)，表示测试用例的数量。

在每个测试用例中：

第一行包含两个整数 $n$ 和 $m$ ($2 \leq n \leq 20000, 2 \leq m \leq 2000, m \leq n$)。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 20000$)。

保证在所有测试用例中，$\sum n \leq 50000$。

输出格式

对于每个测试用例：

输出一行一个整数，表示最小总花费。

1
7 3
1 5 7 2 1 4 8

13