B

题目大意：给定一个大小为 $n$ 的整数数组 $a$。初始时，数组所有元素均被涂为红色。需要执行以下操作： 1. 选择恰好 $k$ 个元素并将其涂为蓝色； 2. 在存在至少一个红色元素的情况下，反复选择任意一个与蓝色元素相邻的红色元素并将其涂为蓝色。涂色成本定义为以下两部分之和： - 初始选择的 $k$ 个元素之和； - 最后一个被涂色的元素的值。需要计算给定数组可能达到的最大涂色成本。

数据范围：$1 \le t \le 10^3$，$2 \le n \le 5000$，$1 \le k < n$，$1 \le a_i \le 10^9$，$\sum n \le 5000$。

思路：