某公司正在进行年末总结,共有 n 位员工在排队轮流进行汇报工作。员工编号分别为 1-n ,其中第 i 位员工汇报工作需要 a_i 分钟。
一次只有一名员工能上台汇报,汇报完便可以直接下班,并且下一位员工可以立刻上来继续汇报,即你可以认为两个员工之间的汇报交接过程不需要时间。
现在,luo 是公司的领导,所有员工汇报完他才能下班。但是 luo 也希望早点下班,所以 luo 可以选择 m 位员工,让他们明天再来汇报工作。
现在 luo 想知道他至少还要等多久才能下班,请你帮帮他
输入
第一行为一个正整数 t ,表示有 t 组测试数据
每组测试数据包括两行
第一行包括两个整数 n , m
第二行包括 n 个整数,第 i 个整数表示 a_i
1 \leq t \leq 1000
1 \leq n \leq 10^5
0 \leq m \leq n
1 \leq a_i \leq 1000
数据保证所有测试数据中的 n 相加和不超过 10^5
输出
输出共 t 行
第 i 行表示第 i 组测试数据的答案
样例
| 标准输入 复制文本 |
3 5 3 1 2 3 4 5 2 2 10 10 5 0 5 4 3 2 1 |
| 标准输出 复制文本 |
3 0 15 |
| 标准输入 复制文本 |
2 10 5 56 69 35 62 65 35 64 79 57 17 6 1 93 34 69 92 25 42 |
| 标准输出 复制文本 |
200 262 |