You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

$n$ 片荷叶排成一排，第 $i$ 片荷叶受伤值为 $a_i$。 有 $k$ 颗魔法石：

1. 每颗魔法石可跳过一片荷叶，被跳过荷叶无伤害；
2. 每跳过一片荷叶，后续所有荷叶受伤值永久+1，效果可叠加。

使用不超过 $k$ 颗魔法石，求跳跳能受到的最少总伤害。

输入格式

多组测试： 第一行整数 $t(1\le t\le 100)$ 表示小河数量。 每条小河两行：

• 一行两个整数 $n,k(1\le n\le 2\cdot 10^5,1\le k\le n)$；
• 一行 $n$ 个整数 $a_1\sim a_n(1\le a_i\le 10^9)$。

输入输出样例 #1

输入 #1

5
4 4
8 7 1 4
4 1
5 10 11 5
7 5
8 2 5 15 11 2 8
6 3
1 2 3 4 5 6
1 1 
7

输出 #1

0
21
9
6
0

数据范围

所有测试荷叶总数不超过 $2 \times 10^5$。

输出格式

每条小河输出最小总伤害。

样例解释

样例1

有4颗魔法石，正好跳过全部4片荷叶，不受任何伤害，所以答案是0。

样例2

只用1颗魔法石时，最优选择是跳过第3片荷叶（基础值11），此时总伤害为21，这是可能的最小值。

样例3

用5颗魔法石跳过5片荷叶后，剩下2片荷叶的总伤害为9。

样例4

用3颗魔法石跳过最后3片荷叶（值4、5、6），剩下荷叶的伤害依次为1、3、5，总和为6。

样例5

只有1片荷叶，用1颗魔法石跳过，不受伤害，答案为0。

数据范围