题目解析

给定一个长度为 $n$ 的数组 $a$，初始全部为红色。
操作分为两个阶段：

1. 恰好选择 $k$ 个元素涂成蓝色（这 $k$ 个元素称为“初始蓝色”）。
2. 反复选择一个有蓝色邻居的红色元素，将其涂蓝，直到全部蓝色为止。

成本定义为：初始选择的 $k$ 个元素的和 $+$ 最后一个被涂蓝的元素的值。
目标：最大化成本。

---

关键观察

1. 成本的上界

成本 = $k$ 个初始蓝色元素的和 $+$ 最后一个被涂蓝的元素
$\le$ 数组中的 $(k+1)$ 个最大元素的和
（因为 $k$ 个初始蓝色元素和最后一个蓝色元素最多覆盖 $k+1$ 个不同位置）。

因此最大可能成本 ≤ 数组中最大的 $k+1$ 个元素的和。

---

2. 何时能达到这个上界？

情况 A：$k \ge 2$

假设数组中最大的 $k+1$ 个元素的位置是 $p_1, p_2, \dots, p_{k+1}$（值从大到小排列）。

我们可以这样构造：

• 初始蓝色选择：$p_1, p_3, p_4, \dots, p_{k+1}$（共 $k$ 个位置，不选 $p_2$）。
• 涂色顺序：
  • 首先由初始蓝色向外扩散，最终除了 $p_2$ 之外，所有元素都会变蓝（因为 $p_2$ 左右邻接位置中有初始蓝色，例如 $p_1$ 或 $p_3$）。
  • 当只剩 $p_2$ 为红色时，它的邻居（$p_1$ 或 $p_3$）已经是蓝色，所以可以最后涂 $p_2$。

这样：

• $k$ 个初始蓝色的和为：除了 $p_2$ 外的 $k$ 个最大元素之和。
• 最后一个涂蓝的元素是 $p_2$（也是最大的 $k+1$ 个元素之一）。

总成本 = $k$ 个最大元素的和 $+$ 第 $k+1$ 大元素的值 = 最大的 $k+1$ 个元素的和。

结论：当 $k \ge 2$ 时，可以达到上界。

---

情况 B：$k = 1$

此时上界是最大的两个元素的和，但能否达到？

• 初始选一个元素 $x$（记为 $a_i$）。
• 最后一个被涂蓝的元素必须是某条路径的终点。
• 由于只有一次初始蓝色，整个涂色过程是从 $a_i$ 向两侧扩散。
• 最后一个涂蓝的元素只能是最左端或最右端的元素。

为什么呢？
想象从 $a_i$ 开始，每次只能涂邻居，那么扩展会像波浪一样左右推进，最后涂色的位置一定是左端 $a_1$ 或右端 $a_n$。

所以：

• 如果初始选 $a_i$（$2 \le i \le n-1$），最后涂的是 $a_1$ 或 $a_n$，成本 = $a_i + \max(a_1, a_n)$。
• 如果初始选 $a_1$，最后涂的是 $a_n$，成本 = $a_1 + a_n$。
• 如果初始选 $a_n$，最后涂的是 $a_1$，成本 = $a_n + a_1$。

这实际上等价于：

• 初始元素必须与最后一个元素在两端相邻（通过扩展路径）？ 不完全是，更简单的观察是：

  最后一个被涂的元素只能是 $a_1$ 或 $a_n$。
  另一个初始蓝色元素可以是任意其他位置。

  因此：

  • 若最后一个涂的是 $a_n$，则初始选 $a_n$ 以外的某个元素 $a_j$（$1 \le j \le n-1$），成本 = $a_j + a_n$，最大时 $a_j$ 取前 $n-1$ 个最大值。
  • 若最后一个涂的是 $a_1$，则初始选 $a_1$ 以外的某个元素 $a_j$（$2 \le j \le n$），成本 = $a_j + a_1$，最大时 $a_j$ 取后 $n-1$ 个最大值。

  但注意最后一个被涂蓝的必须是 $a_1$ 或 $a_n$，不一定是两个最大值的和。

经过更严谨的分析（如标程所示），$k=1$ 时的最优解是以下两种可能的最大值：

1. 最后一个涂 $a_n$：初始选前 $n-1$ 个元素中的最大值（即 $\max(a_1 \dots a_{n-1})$），成本 = $\max(a_1 \dots a_{n-1}) + a_n$。
2. 最后一个涂 $a_1$：初始选后 $n-1$ 个元素中的最大值（即 $\max(a_2 \dots a_n)$），成本 = $\max(a_2 \dots a_n) + a_1$。

取两者较大值。

---

3. 特殊情况 $k = n-1$（$k \ge 2$ 时自动包括）

此时 $k+1 = n$，最大 $k+1$ 个元素就是整个数组的和，即能达到整个数组的和。

检查标程：
当 $k > 1$ 时，直接取前 $k+1$ 大元素的和，这包括了 $k = n-1$ 的情况，此时就是所有元素的和，符合直觉。

---

算法步骤

1. 读入 $t$。
2. 对每个测试用例：
   • 读入 $n, k$ 和数组 $a$。
   • 若 $k > 1$：
     • 将 $a$ 从大到小排序。
     • 答案 = 前 $k+1$ 个元素的和。
   • 若 $k = 1$：
     • $l = \max(a_1, a_2, \dots, a_{n-1})$
     • $r = \max(a_2, a_3, \dots, a_n)$
     • 答案 = $\max(l + a_n, r + a_1)$
3. 输出答案。

---

时间复杂度

• 排序 $O(n \log n)$
• 总 $n$ 不超过 $5000$，可轻松通过。

---

例子验证

例1

$n=3, k=1, a=[1,2,3]$
$l = \max(1,2) = 2,\ r = \max(2,3) = 3$
答案 = $\max(2+3, 3+1) = \max(5,4) = 5$，匹配输出。

例2

$n=5, k=2, a=[4,2,3,1,3]$
排序降序：$[4,3,3,2,1]$
前 $k+1=3$ 个元素和 $=4+3+3=10$，匹配输出。

例3

$n=4, k=3, a=[2,2,2,2]$
$k>1$，排序降序 $[2,2,2,2]$
前 $k+1=4$ 个元素和 $=2+2+2+2=8$，匹配输出。

---

总结

• $k \ge 2$ 时，直接取前 $k+1$ 大元素的和。
• $k = 1$ 时，分两种情况取最大值，分别对应最后涂 $a_n$ 或 $a_1$。
• 该构造方法能达到理论最大值，因此贪心 + 构造即可。