EOJ-自适应编程学习平台

任务背景 罗德岛正在进行战术单元协同作战训练。现有n名干员排成一列，每位干员都有一个作战效能值$a_i$。凯尔希医生需要从中选出k组相邻两人小队进行实战演练。

训练规则

• 每组小队的协同效能为两人效能之和
• 选出的小队之间不能共用同一干员（即不能重叠）
• 目标是最小化所有小队的总协同效能

第一行输入一个整数$T(1\leq T \leq 10^5)$，代表有$T$组样例

每组样例第一行输入两个整数$n, k(1\leq n \leq 10^6, 0\leq k \leq \lfloor \frac{n}{2} \rfloor)$

第二行输入输入$n$个整数$a_1,a_2,\cdots,a_n(-10^9\leq a_i \leq 10^9)$

对于所有数据$\sum n \leq 10^6$

一个整数，表示k组小队的最小总协同效能