CF1969C Minimizing the Sum

给定一个长度为 $n$ 的整数数组 $a$。 你可以进行如下操作：选择数组中的一个元素，并将其替换为任意一个相邻元素的值。 例如，如果 $a=[3, 1, 2]$，你可以通过一次操作得到 $[3, 3, 2]$、$[3, 2, 2]$ 或 $[1, 1, 2]$，但不能得到 $[2, 1, 2]$ 或 $[3, 4, 2]$。 你的任务是计算，在最多可以进行上述操作 $k$ 次的情况下，数组元素之和的最小可能值。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 3 \cdot 10^5$；$0 \le k \le 10$）。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）。 输入的额外约束：所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示在最多进行 $k$ 次操作后，数组元素之和的最小可能值。

在第一个样例中，一种可能的操作序列为：$[3, 1, 2] \rightarrow [1, 1, 2]$。 在第二个样例中，你无需进行任何操作。 在第三个样例中，一种可能的操作序列为：$[2, 2, 1, 3] \rightarrow [2, 1, 1, 3] \rightarrow [2, 1, 1, 1]$。 在第四个样例中，一种可能的操作序列为：$[4, 1, 2, 2, 4, 3] \rightarrow [1, 1, 2, 2, 4, 3] \rightarrow [1, 1, 1, 2, 4, 3] \rightarrow [1, 1, 1, 2, 2, 3]$。 由 ChatGPT 4.1 翻译