## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Traps Codeforces Solution | Codeforces Problem Solution 2022

D. Traps
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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 $\left({a}_{i}+3\right)$ 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.

Input

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},\dots ,{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}$.

Output

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.