Description

题目描述

给你一个长度为 $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

输入 #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]$ .

$30 \%$的数据，$1 \le \sum n \le 1000$

$100 \%$的数据，$1 \le \sum n \le3\times 10^5,A_i \le 10^9$