题目描述

黄老师给徐老师列了一个练习题单，一共包含 $n$ 题，编号 $1 \sim n$，让徐老师依次按顺序完成

每次完成题目后，徐老师的水平会有一定的提升，于是黄老师设计了一个计算模型

计算徐老师按顺序依次完成每道题时，完成第 $i$ 题需要 $a_i$ 分钟

但是聪明的徐老师动了动他聪明的脑袋瓜，决定跳过几道题不做（最多 $k$ 题）

但是由于黄老师的模型预测时间是根据徐老师依次做题带来的水平提升估计的时间

所以如果徐老师跳过了其中一道题，会导致后续所有题目的预测做题时间增加

比如徐老师跳过了第 $i$ 题，那么会导致后续所有的题目（$i + 1 \sim n$）完成时间 $+ 1$

换句话说，如果徐老师现在要完成第 $j$ 题，前面已经跳过了 $2$ 道题没做，那么第 $j$ 题的题目完成时间将会是 $a_j + 2$

现在徐老师想知道，怎么安排跳过和做题可以让他完成题目的总用时最少？

这样他就可以快乐的去打游戏了

输入格式

输入第一行一个正整数 $T$ 表示测试数据数量

对于每组测试数据：

输入第一行包含两个整数 $n,k$ 表示题目数量和最多跳过的题目数量

接下来一行包含 $n$ 个整数 $a_i$，表示依次完成每道题需要的时间

输出格式

对于每组测试数据，输出一行包含一个整数表示最小花费的时间

数据范围

对于所有数据保证 $1 \leq k \leq n,0 \leq a_i \leq 1000$

样例输入1

2
4 4
8 7 1 4
4 1
5 10 11 5

样例输出1

0
21

样例解释1

对于第一组测试数据：全部跳过，总用时为 $0$

对于第二组测试数据：跳过第三题，总用时为 $5+10+0+(5+1)=21$