A15127 · Traps · GESP考级

题目描述

There are $n$ traps numbered from $1$ to $n$ . You will go through them one by one in order. The $i$ -th trap deals $a_i$ base damage to you. Instead of going through a trap, you can jump it over. You can jump over no more than $k$ traps. If you jump over a trap, it does not deal any damage to you. But there is an additional rule: if you jump over a trap, all next traps damages increase by $1$ (this is a bonus damage). Note that if you jump over a trap, you don't get any damage (neither base damage nor bonus damage). Also, the bonus damage stacks so, for example, if you go through a trap $i$ with base damage $a_i$ , and you have already jumped over $3$ traps, you get $(a_i + 3)$ damage. You have to find the minimal damage that it is possible to get if you are allowed to jump over no more than $k$ traps.

The input consists of multiple test cases. The first line contains a single integer $t$ ( $1 \le t \le 100$ ) — the number of test cases. Description of the test cases follows. The first line of each test case contains two integers $n$ and $k$ ( $1 \le n \le 2 \cdot 10^5$ , $1 \le k \le n$ ) — the number of traps and the number of jump overs that you are allowed to make. The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le 10^9$ ) — base damage values of all traps. It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .

For each test case output a single integer — the minimal total damage that it is possible to get if you are allowed to jump over no more than $k$ traps.

输入 #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