Minimizing the Sum
Description
You are given an integer array $a$ of length $n$.
You can perform the following operation: choose an element of the array and replace it with any of its neighbor's value.
For example, if $a=[3, 1, 2]$, you can get one of the arrays $[3, 3, 2]$, $[3, 2, 2]$ and $[1, 1, 2]$ using one operation, but not $[2, 1, 2$] or $[3, 4, 2]$.
Your task is to calculate the minimum possible total sum of the array if you can perform the aforementioned operation at most $k$ times.
The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 3 \cdot 10^5$; $0 \le k \le 10$).
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).
Additional constraint on the input: the sum of $n$ over all test cases doesn't exceed $3 \cdot 10^5$.
For each test case, print a single integer — the minimum possible total sum of the array if you can perform the aforementioned operation at most $k$ times.
Input
The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 3 \cdot 10^5$; $0 \le k \le 10$).
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).
Additional constraint on the input: the sum of $n$ over all test cases doesn't exceed $3 \cdot 10^5$.
Output
For each test case, print a single integer — the minimum possible total sum of the array if you can perform the aforementioned operation at most $k$ times.
4
3 1
3 1 2
1 3
5
4 2
2 2 1 3
6 3
4 1 2 2 4 3
4
5
5
10
Note
In the first example, one of the possible sequences of operations is the following: $[3, 1, 2] \rightarrow [1, 1, 2$].
In the second example, you do not need to apply the operation.
In the third example, one of the possible sequences of operations is the following: $[2, 2, 1, 3] \rightarrow [2, 1, 1, 3] \rightarrow [2, 1, 1, 1]$.
In the fourth example, one of the possible sequences of operations is the following: $[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]$.