题目描述

给定一个长度为 $N$ 的自然数序列。其中一部分位置一开始没有被病毒感染，用数值 $0$ 表示；其余位置被感染，非零数值表示将该位置清除病毒所需的代价。

你可以清除一部分被感染的位置。一个位置在某个时刻可以被清除，当且仅当它至少有一个相邻位置已经是未感染状态。清除一个位置后，它的代价会加入总代价，且该位置变为未感染位置，从而可能继续影响它的相邻位置。

要求最终序列中恰好有 $K$ 个未感染位置，包含初始时就未感染的位置。求最小总代价。

输入格式

第一行包含整数 $T$，表示测试组数。

每组测试包含两行：

第一行两个整数 $N,K$。

第二行 $N$ 个自然数，表示序列元素。

输出格式

包含 $T$ 行。每行输出一个整数，表示对应测试中使最终恰好有 $K$ 个未感染位置的最小总代价。

数据范围与限制

• $1\le T\le 4$
• $1\le K\le N\le 2000$
• 序列元素为自然数，非零元素表示清除代价

子任务：

• 10 分：$N\le 80$
• 20 分：$N\le 200$
• 10 分：初始序列中恰有 1 个未感染位置
• 10 分：初始序列中恰有 2 个未感染位置

样例

输入

2
8 5
9 1 4 4 0 1 3 9
6 4
1 0 2 0 1 1

输出

10
2

样例解释

第一组测试可以清除下标 $2,3,4,6$ 的位置，总代价为 $1+4+4+1=10$。

第二组测试可以清除下标 $5,6$，总代价为 $2$；也存在其它总代价相同的方案。