最小化数组和

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定长度为 $n$ 的整数数组 $a$。一次操作可以选择一个元素，并把它替换成任意一个相邻元素当前的值。你最多可以进行 $k$ 次操作，求数组元素和的最小可能值。

输入格式

第一行包含测试用例数 $t$。每组第一行包含 $n,k$，第二行包含 $n$ 个整数 $a_1,\ldots,a_n$。

输出格式

每组输出一行最小可能元素和。

样例输入 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

数据范围

$1\le t\le10^4$，$1\le n\le3\times10^5$，$0\le k\le10$，$1\le a_i\le10^9$，所有测试用例的 $n$ 之和不超过 $3\times10^5$。