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

荒诞帖农场

题目描述

乐柠兔准备了 $n$ 篇帖子草稿，第 $i$ 篇草稿的荒诞度为 $a_i$，荒诞度可能为负数。

他必须按照原顺序，从这 $n$ 篇草稿中恰好选择 $m$ 篇发布。

设选出的荒诞度依次为

并规定 $b_0=0$。

发布第 $i$ 篇被选中的帖子时，获得的得分变化量为

得分可以减少，也允许变成负数。

最终得分为

请计算，在保持原顺序并恰好选择 $m$ 篇草稿的条件下，能够得到的最大最终得分。

输入格式

第一行输入一个整数 $T$，表示测试用例数量。

对于每组测试数据：

第一行输入两个整数 $n,m$。

第二行输入 $n$ 个整数

输出格式

对于每组测试数据，输出一行一个整数，表示最大最终得分。

样例

样例输入 #1

6
5 3
0 8 1 7 3
4 3
0 -4 10 -2
4 2
0 5 -2 4
6 3
0 9 8 7 6 5
1 1
7
3 2
5 -100 4

样例输出 #1

20
34
10
15
7
108

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1\le T\le10^4$；
• $1\le m\le n\le2\times10^5$；
• $-10^7\le a_i\le10^7$；
• 所有测试用例的 $n$ 之和不超过 $2\times10^5$。

固定设置 $20$ 个测试点。

• 特殊性质 A：保证 $m=1$。
• 特殊性质 B：保证所有 $a_i\ge0$。