← 返回题目列表

Codeforces · 1969/C

C. 最小化总和

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

给你一个长度为$$$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$$$ 次,则数组的最小可能总和。

示例

输入 #1

4
3 1
3 1 2
1 3
5
4 2
2 2 1 3
6 3
4 1 2 2 4 3

输出 #1

4
5
5
10

注意

在第一个示例中,可能的操作序列之一如下:$$$[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]$$$。