爱丽丝（Alice）和鲍勃（Bob）得到了一个长度为 $N$ 的整数数组 $A$。

爱丽丝选择一个长度为 $N$ 且恰好含有 $K$ 个 $1$ 的 01 字符串 $B$，该字符串在整个游戏过程中保持不变。

在任何时刻，下标 $i$ 是受保护的当且仅当 $B_i = 1$，鲍勃可以选择下标 $i$ 当且仅当 $B_i = 0$。

鲍勃进行零次或多次操作。鲍勃的初始得分为 0。

在一次操作中，鲍勃选择一个满足以下条件的下标 $i$：

• $B_i = 0$；
• $1 \le i \le |A|$。

鲍勃将当前的值 $A_i$ 累加到他的得分中，并将该元素从 $A$ 中移除。每次删除后，$|A|$ 的值减少 1，且 $A$ 中剩余的元素将重新从 1 到 $|A|$ 进行编号。

因此，$B$ 是作用于当前的下标位置，而不是固定的元素身份。在元素移动后，同一个元素可能会变得受保护或可移除。

如果鲍勃在多次操作中选择的下标依次为 $P_1, P_2, \dots, P_m$，则它们必须是非递增的，即：

$$P_1 \ge P_2 \ge \dots \ge P_m$$

鲍勃可以多次选择相同的下标。

爱丽丝希望最小化鲍勃的得分，而鲍勃希望最大化他的得分。

求在双方都采取最优策略的情况下，鲍勃的最终得分。

输入格式

输入按以下格式给出：

T
N K
A1 A2 ... AN
...

输出格式

对于每个测试用例，输出一个整数，表示鲍勃的最终得分。

数据范围

• 所有输入值均为整数。
• $1 \le T \le 10^5$
• $1 \le N \le 6000$
• $0 \le K \le N$
• $-10^9 \le A_i \le 10^9$
• 保证所有测试用例中 $N$ 的总和不超过 $10^6$。
• 保证所有测试用例中 $N^2$ 的总和不超过 $6000^2$。

样例

输入样例 1

6
5 2
4 -1 7 -3 2
4 0
-5 -2 -1 -3
4 4
2 -7 5 1
1 0
-1
2 1
0 1
3 1
1 -1 1

输出样例 1

7
0
0
0
1
1

说明

• 测试用例 1：爱丽丝可以选择 $B = 10001$。此时，鲍勃最初可以使用的下标为 2、3 和 4，对应的值分别为 $-1$、7 和 $-3$。鲍勃可以通过选择一次下标 3（得分增加 7）来确保获得 7 分。在此之后，下一次选择的任何下标都必须不超过 3，因此不能选择下标 4，且任何后续的合法操作都只能增加非正数的值。爱丽丝可以确保鲍勃无法获得超过 7 的分数，因此答案为 7。
• 测试用例 2：由于 $K = 0$，爱丽丝别无选择，只能选择 $B = 0000$。鲍勃可以使用所有下标，但数组中的每个值都是负数。任何操作都会降低鲍勃的得分，因此鲍勃的最优策略是不进行任何操作。因此，答案为 0。
• 测试用例 3：由于 $K = N$，爱丽丝别无选择，只能选择 $B = 1111$。每个位置都受到保护，因此鲍勃根本无法进行任何合法操作。因此，鲍勃的得分为 0。