该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

LHao 喜欢参与 codeforces 的比赛。某次新生赛他做了一道叫 kidding的紫名路 的题目，但是他赛时并没有做出来。于是把这道题改编成了一道他更擅长的题。让你们来解决。

题目描述

现在 LHao 打了 $n$ 场比赛，每场比赛都会有评分变化，可加可减，但当减到小于 $0$ 时，rate 会自动变成 $0$，也就是每计算完一次rate之后rate=max(rate,0) 。初始 rate 是 $0$ 。现在 LHao 也黑进了 codeforces 的后台，他可以精准的删去恰好 $k$ 场的评级变化，现在他想知道删去 $k$ 次评级变化后他的最大 rate 是多少。

注：最大rate指所达到过的rate中的最大值。

输入格式

第一行包含整数 $t$ $(1\leq t\leq 10^4)$，表示有 $t$ 组测试数据；

每组测试数据占两行。

第一行输入 $n$ $(0\leq n\leq 10^4)$ 和 $k$ $(0\leq k\leq 10^4)$，分别表示 LHao 参加比赛数和要删掉的场次数，第二行输入 $n$ 个整数 $a_1,a_2...a_n$ $(0\leq |a_i|\leq 10^9)$表示每场的评分变化。

保证 $T$ 组数据的 $n$ 之和不超过 $10^4$。

输出格式

每组数据输出一行结果，一个整数，表示删去恰好 $k$ 场后 LHao 的最大 rate。

样例

1
10 1
1 1 1 -9 1 1 1 -9 1 1

6

1
9 3
0 -1000000 0 -100000 7  -100 2 -1 1

10

限制与提示

本题测试点较多，测的慢是正常的。