← 返回题目列表

Codeforces · 2075/B

B. 数组重新着色

中文机器翻译题面 查看原题

给定一个整数数组 $$$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$$$。

输出

对于每个测试用例,打印一个整数 - 给定数组的最大可能绘制成本。

示例

输入
复制

3
3 1
1 2 3
5 2
4 2 3 1 3
4 3
2 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$$$。