给定一个整数数组 $$$a$$$,大小为 $$$n$$$。最初,数组的所有元素都被涂成红色。
您必须准确选择数组的 $$$k$$$ 元素并将它们涂成蓝色。然后,虽然至少有一个红色元素,但您必须选择任何具有蓝色邻居的红色元素并将其设为蓝色。
绘制数组的成本定义为第一个 $$$k$$$ 选择的元素和最后一个绘制元素的总和。
您的任务是计算给定数组的最大可能绘制成本。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^3$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 5000$$$; $$$1 \le k \lt n$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。
对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。
输出
对于每个测试用例,打印一个整数 - 给定数组的最大可能绘制成本。
示例
输入复制
33 11 2 35 24 2 3 1 34 32 2 2 2
输出复制
5 10 8
注意
在第一个示例中,您可以首先为 $$$2$$$-nd 元素着色,然后按 $$$1, 3$$$ 的顺序为元素着色。那么喷漆的费用就等于$$$2+3=5$$$。
在第二个示例中,您可以首先为元素 $$$1$$$ 和 $$$5$$$ 着色,然后按 $$$2, 4, 3$$$ 的顺序为元素着色。那么喷漆的费用就等于$$$4+3+3=10$$$。
在第三个示例中,您可以首先为元素 $$$2, 3, 4$$$ 着色,然后为 $$$1$$$-st 元素着色。那么绘画费用就等于$$$2+2+2+2=8$$$。