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.


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


-----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.


-----Examples-----

Input
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
Output
0
21
9
6
0


-----Note-----

In the first test case it is allowed to jump over all traps and take $0$ damage.

In the second test case there are $5$ ways to jump over some traps:

Do not jump over any trap.

Total damage: $5 + 10 + 11 + 5 = 31$.

Jump over the $1$-st trap.

Total damage: $\underline{0} + (10 + 1) + (11 + 1) + (5 + 1) = 29$.

Jump over the $2$-nd trap.

Total damage: $5 + \underline{0} + (11 + 1) + (5 + 1) = 23$.

Jump over the $3$-rd trap.

Total damage: $5 + 10 + \underline{0} + (5 + 1) = 21$.

Jump over the $4$-th trap.

Total damage: $5 + 10 + 11 + \underline{0} = 26$.

To get minimal damage it is needed to jump over the $3$-rd trap, so the answer is $21$.

In the third test case it is optimal to jump over the traps $1$, $3$, $4$, $5$, $7$:

Total damage: $0 + (2 + 1) + 0 + 0 + 0 + (2 + 4) + 0 = 9$.

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

Sorting

Constructive algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [x + y for (x, y) in enumerate(a)]
	print(sum(sorted(b)[:n - k]) - (n - k) * (n - k - 1) // 2)


I = input
R = lambda : map(int, I().split())
for i in range(int(I())):
	(n, k) = R()
	a = sorted([v + i for (i, v) in enumerate(R())])
	print(sum(a[:-k]) - (n - k) * (0 + n - k - 1) // 2)


r = int(input())
for i in range(r):
	(p, k) = map(int, input().split())
	g = list(map(int, input().split()))
	h = [x + y for (x, y) in enumerate(g)]
	print(sum(sorted(h)[:p - k]) - (p - k) * (p - k - 1) // 2)


kvs = int(input())
for _ in range(kvs):
	(c, d) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [x + y for (x, y) in enumerate(a)]
	print(sum(sorted(b)[:c - d]) - (c - d) * (c - d - 1) // 2)


def solve(n, k, arr):
	if k >= n:
		print(0)
		return
	first_k = k
	res = []
	ans = sum(arr)
	arr = arr[::-1]
	damage_idx = []
	for i in range(len(arr)):
		damage_idx.append(i - arr[i])
	damage_idx.sort()
	for i in range(k):
		ans += damage_idx[i]
	print(int(ans - k * (k - 1) / 2))

def get_input():
	first_line = input()
	n = int(first_line.split()[0])
	k = int(first_line.split()[1])
	arr = list(map(int, input().split()))
	return (n, k, arr)
t = int(input())
for i in range(t):
	(n, k, arr) = get_input()
	solve(n, k, arr)


def resi():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = sum(a)
	for i in range(n):
		a[i] = a[i] - (n - (i + 1))
	a.sort()
	print(s - sum(a[-k:]) - k * (k - 1) // 2)
	return
for _ in range(int(input())):
	resi()


for _ in range(int(input())):
	(trap, jump) = map(int, input().split())
	temp = list(map(int, input().split()))
	print(sum(sorted([temp[i] + i for i in range(trap)])[:trap - jump]) - (trap - jump) * (trap - jump - 1) // 2)


def find(n, k, a):
	if k >= n:
		return 0
	carry = [a[i] + i + 1 for i in range(n)]
	carry.sort()
	carry.reverse()
	skip = sum(carry[:k])
	return sum(a) + n * k - int((k - 1) * k / 2) - skip
case = int(input())
for _ in range(case):
	line = input().split()
	(n, k) = (line[0], line[1])
	raw = input().split()
	a = [int(elem) for elem in raw]
	print(find(int(n), int(k), a))


t = int(input())
while t:
	t -= 1
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	diff = [x - (n - 1 - i) for (i, x) in enumerate(a)]
	diff.sort()
	ans = sum(a)
	ans -= sum(diff[-k:])
	ans -= k * (k - 1) // 2
	print(ans)


def main():
	tc = int(input())
	for _ in range(tc):
		(n, k) = map(int, input().split())
		arr = [int(a) for a in input().split()]
		cost = sum(arr)
		removals = []
		for i in range(n):
			removals.append(arr[i] - (n - i - 1))
		removals.sort(reverse=True)
		for i in range(k):
			cost -= removals[i]
		print(cost - k * (k - 1) // 2)
main()


def dTraps(n, k, l):
	costs = []
	for i in range(n):
		costs.append(n - i - 1 - l[i])
	costs.sort()
	c = 0
	for i in range(k):
		c += costs[i]
	c -= k * (k - 1) // 2
	print(sum(l) + c)
t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	dTraps(n, k, l)
	t = t - 1


import collections
from math import ceil, gcd, sqrt, log
INF = float('inf')
mod = 1000000007

def solve():
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	total_damage = sum(A)
	additional_damage_removed = k * (k - 1) // 2
	removed = []
	for i in range(n):
		ok = A[i] - (n - i - 1)
		removed.append(ok)
	removed.sort(reverse=True)
	net_removed_damage = 0
	for i in range(k):
		net_removed_damage += removed[i]
	ans = total_damage - net_removed_damage - additional_damage_removed
	print(ans)
t = int(input())
while t != 0:
	solve()
	t -= 1


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = [int(x) for x in input().split()]

	def solve(arr, n, k):
		if k == n:
			return 0
		sumi = 0
		for i in range(n):
			sumi += arr[i]
			arr[i] -= n - i - 1
		if k == 0:
			return sumi
		arr.sort(reverse=True)
		for i in range(k):
			sumi -= arr[i]
		sumi -= k * (k - 1) // 2
		return sumi
	print(solve(arr, n, k))


def find_minimal_damage_count(n, jumps, attacks):
	damageCount = 0
	if n == jumps:
		return damageCount
	for i in range(n):
		damageCount += attacks[i]
		attacks[i] += i + 1
	attacks.sort()
	attacks.reverse()
	for i in range(jumps):
		damageCount -= attacks[i]
		damageCount += n - i
	return damageCount
t = int(input())
for i in range(t):
	lens = input().split(' ')
	n = int(lens[0])
	jumps = int(lens[1])
	attacks = list(map(int, input().split(' ')))
	print(str(find_minimal_damage_count(n, jumps, attacks)))


def r():
	return list(map(int, input().split()))
for i in range(int(input())):
	(a, b) = r()
	c = r()
	e = []
	for i in range(a):
		e.append(a - i - 1 - c[i])
	print(sum(c) - b * (b - 1) // 2 + sum(sorted(e)[:b]))


def solve():
	(n, k) = map(int, input().split())
	a = tuple(map(int, input().split()))
	dmg_bonus = [i for i in range(n)]
	dmg_bonus.sort(key=lambda x: a[x] + x, reverse=True)
	jump = [False] * n
	for i in range(k):
		jump[dmg_bonus[i]] = True
	ans = 0
	bonus = 0
	for i in range(n):
		if jump[i]:
			bonus += 1
		else:
			ans += a[i] + bonus
	print(ans)
t = int(input())
for _ in range(t):
	solve()


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	B = [A[i] - N + i for i in range(N)]
	B.sort(reverse=True)
	total = sum(A) - K * (K + 1) // 2
	for i in range(K):
		total -= B[i]
	print(total)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	d = list(map(int, input().split()))
	sm = sum(d)
	for i in range(n):
		d[i] = -d[i] + (n - 1 - i)
	d.sort()
	for i in range(k):
		sm += d[i] - i
	print(sm)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	otv = sum(a)
	esl_per = [0] * n
	for i in range(n):
		esl_per[i] = a[i] - (n - 1 - i)
	kaz = k * (k - 1) // 2
	esl_per.sort(reverse=True)
	if n == k:
		print(0)
	else:
		print(otv - sum(esl_per[:k]) - kaz)


for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	A = [int(i) for i in input().split()]
	res = sum(A) - k * (k - 1) // 2
	for i in range(n):
		A[i] -= n - i - 1
	A.sort()
	for i in range(k):
		res -= A[-i - 1]
	print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = [int(i) for i in input().split()]
	ll = sorted([-l[i] + (n - 1 - i) for i in range(n)])
	base = sum(l)
	poss = [base]
	for i in range(k):
		base += ll[i] - i
		poss.append(base)
	print(min(poss))


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	v = list(map(int, input().split()))
	ans = 0
	for i in range(0, n):
		ans += v[i]
		v[i] = -v[i] + n - i
	v.sort()
	for i in range(0, k):
		ans += v[i]
	ans -= k * (k + 1) // 2
	print(ans)
	t -= 1


import math
for _ in range(int(input())):
	(trap, jump) = map(int, input().split())
	temp = list(map(int, input().split()))
	z = {}
	for i in range(trap):
		z[i] = temp[i] + i
	k = sorted(list(z.values()))
	total = 0
	for i in range(trap - jump):
		total += k[i]
	a = trap - jump
	total -= a * (a - 1) // 2
	print(total)


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	l = [int(x) for x in input().split()]
	ans = []
	if n <= k:
		print(0)
	else:
		for (i, j) in enumerate(l):
			ans.append(j - n + i + 1)
		a = sorted(ans)
		sumu = sum(l)
		t = k
		for i in range(k):
			sumu -= a[n - i - 1]
		print(sumu - t * (t - 1) // 2)


T = int(input())
while T:
	T -= 1
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	sum = 0
	for i in range(n):
		sum += a[i]
		a[i] += i + 1
	a.sort(reverse=True)
	for i in range(k):
		sum -= a[i] - n + k - (i + 1)
	print(sum)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ans += arr[i]
		arr[i] += i + 1
	arr.sort(reverse=True)
	for i in range(k):
		ans -= arr[i]
	for i in range(k):
		ans += n
		ans -= i
	print(ans)


t = int(input())
for test in range(t):
	(n, k) = map(lambda x: int(x), input().split())
	a = list(map(lambda x: int(x), input().split()))
	total = sum(a)
	costs = [0] * n
	for i in range(n):
		costs[i] = a[i] - (n - i - 1)
	costs.sort(reverse=True)
	for i in range(k):
		if costs[i] + i > 0:
			total -= costs[i] + i
	print(total)


def get_minimum_damage(trap_count: int, base_damage: list, jumps: int):
	if trap_count <= jumps:
		return 0
	damage_loss_pairs = [(idx, val, val - (trap_count - idx) + 1) for (idx, val) in enumerate(base_damage)]
	damage_loss_pairs.sort(key=lambda x: x[2], reverse=True)
	jumbed_trap = damage_loss_pairs[:jumps]
	other_trap = damage_loss_pairs[jumps:]
	total_penalty = sum([trap_count - trap[0] - (jumps - idx) for (idx, trap) in enumerate(jumbed_trap)])
	damage_gained = sum(map(lambda x: x[1], other_trap)) + total_penalty
	return damage_gained
no_test = int(input())
for _ in range(no_test):
	(num, no_of_jumsps) = map(int, input().split())
	numbers = list(map(int, input().split()))
	damages = get_minimum_damage(num, numbers, no_of_jumsps)
	print(damages)


for inh in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	pen = [0] * n
	for i in range(n):
		pen[i] = a[i] - (n - 1 - i)
	ref = pen.copy()
	ref.sort(reverse=True)
	ref = ref[:k]
	j = ref.count(ref[-1])
	for i in range(n):
		if pen[i] > ref[-1]:
			a[i] = 0
		elif pen[i] == ref[-1]:
			if j > 0:
				a[i] = 0
				j -= 1
	ans = 0
	penalty = 0
	for i in range(n):
		ans += a[i]
		if a[i] == 0:
			penalty += 1
		else:
			ans += penalty
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	costs = []
	for i in range(n):
		costs.append(n - i - 1 - l[i])
	costs.sort()
	c = 0
	for i in range(k):
		c += costs[i]
	c -= k * (k - 1) // 2
	print(sum(l) + c)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	traps = list(map(int, input().split()))
	if k >= n:
		print(0)
		continue
	sortedred = []
	for i in range(n):
		sortedred.append((i, traps[i] - (n - i - 1)))
	sortedred.sort(key=lambda x: x[1], reverse=True)
	totalred = 0
	j = 0
	for i in range(k):
		totalred += sortedred[i][1]
		j += 1
	print(sum(traps) - totalred - j * (j - 1) // 2)


import sys
sys.setrecursionlimit(10 ** 5)

def pro(arr, k):
	n = len(arr)
	tot = sum(arr)
	lst = []
	for i in range(n):
		lst.append((arr[i] + i, i))
	lst.sort(reverse=True)
	for i in range(k):
		arr[lst[i][1]] = -1
	x = 0
	ans = 0
	for i in range(n):
		if arr[i] != -1:
			ans += arr[i] + x
		else:
			x += 1
	print(ans)
t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	pro(arr, k)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	L = list(map(int, input().split()))
	D = []
	for i in range(n):
		D.append((L[i] - n + 1 + i, i))
	D.sort(reverse=True)
	ans = sum(L)
	for i in range(k):
		ans -= D[i][0]
	ans -= k * (k - 1) // 2
	print(ans)


def getMin(d, k):
	l = []
	for i in range(len(d)):
		penalty = len(d) - i
		l.append((d[i] - penalty, i))
	l.sort(reverse=True)
	total = 0
	indices = set([l[i][1] for i in range(k, len(d))])
	penalty = 0
	for i in range(len(d)):
		if i in indices:
			total += d[i] + penalty
		else:
			penalty += 1
	return total
cases = int(input())
for i in range(cases):
	(n, k) = map(int, input().split())
	d = list(map(int, input().split()))
	print(getMin(d, k))


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	Arr = list(map(int, input().split()))
	if N == K:
		print(0)
		continue
	Temp = []
	for i in range(N):
		Temp.append([Arr[i] - (N - i - 1), i])
	Temp.sort(key=lambda x: x[0])
	Allowed = [False] * N
	for i in range(N - K):
		Allowed[Temp[i][1]] = True
	Answer = 0
	Jump = 0
	for i in range(N):
		if Allowed[i]:
			Answer += Arr[i] + Jump
		else:
			Jump += 1
	print(Answer)


test = int(input())
while test:
	test -= 1
	(n, k) = [int(x) for x in input().split()]
	arr = [(int(x), i) for (i, x) in enumerate(input().split())]
	check = []
	for (val, index) in arr:
		check.append((val - n + index, index))
	check.sort(reverse=True)
	index = set()
	for i in range(k):
		index.add(check[i][1])
	ans = 0
	bonus = 0
	for i in range(n):
		(val, pos) = arr[i]
		if pos in index:
			bonus += 1
		else:
			ans += val
			ans += bonus
	print(ans)


from collections import deque

def solve():
	if k == n:
		return 0
	if k == 0:
		res = sum(arr)
		return res
	vals = [arr[i] + i - n + k + 1 for i in range(n - k, n)]
	vals.sort()
	second = [(arr[i] - (n - k - 1 - i), -i) for i in range(n - k)]
	second.sort(reverse=True)
	res = 0
	ind = 0
	for i in range(len(second)):
		if ind < k and second[i][0] > vals[ind]:
			res += vals[ind] + arr[abs(second[i][1])] - second[i][0]
			ind += 1
		else:
			res += arr[abs(second[i][1])]
	return res
T = int(input())
for t in range(T):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	ans = solve()
	print(ans)


for T in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	l = [int(i) for i in input().split()]
	l2 = [(l[i] - (n - i - 1), i) for i in range(n)]
	l2.sort()
	skipped = {j[1] for j in l2[-k:]}
	damage = 0
	s = k
	for (i, v) in enumerate(l):
		if i in skipped:
			damage += n - i - s
			s -= 1
		else:
			damage += v
	print(damage)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	narr = [(arr[i] - (n - i - 1), i) for i in range(n)]
	narr.sort(reverse=True)
	narr = narr[:k]
	indexs = list(map(lambda x: x[1], narr))
	indexs.sort()
	ls = len(indexs)
	(j, k, ans) = (0, 0, 0)
	for i in range(n):
		if j < ls:
			if i == indexs[j]:
				k += 1
				j += 1
				continue
		ans += k + arr[i]
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	li = []
	for i in range(n):
		li.append([a[i] + i, i])
	li.sort(reverse=True)
	nli = [0 for i in range(n)]
	for i in range(k):
		nli[li[i][1]] = 1
	c = 0
	ans = 0
	for i in range(n):
		if nli[i] == 0:
			ans += a[i] + c
		else:
			c += 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, list(input().split()))
	l = list(map(int, input().split()))
	ar = [(i, -l[i] + n - i - 1) for i in range(n)]
	ar.sort(key=lambda x: (x[1], x[0]))
	ans = 0
	s = sum(l)
	for i in range(k):
		ans += n - ar[i][0] - i - 1
		s -= l[ar[i][0]]
	print(s + ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	t = []
	for i in range(n):
		t.append([l[i] - (n - i - 1), i])
	t = sorted(t)[::-1]
	x = [0 for _ in range(n)]
	for i in range(k):
		x[t[i][1]] = 1
	ans = 0
	p = 0
	for i in range(n):
		if x[i] == 1:
			p += 1
		else:
			ans += l[i] + p
	print(ans)


from posixpath import split
t = int(input())
while t > 0:
	r = input().split()
	(n, k) = (int(r[0]), int(r[1]))
	a = input().split()
	for i in range(n):
		a[i] = int(a[i])
	b = []
	for i in range(n):
		b.append((a[i] - n + i, i))
	b.sort()
	ans = sum(a)
	m = sum(a)
	for i in range(n - 1, n - k - 1, -1):
		m = m - a[b[i][1]] + n - b[i][1] - 1 - (n - i - 1)
		ans = min(ans, m)
	print(ans)
	t -= 1


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if k == n:
		print(0)
	else:
		arr = []
		for i in range(n):
			arr.append([a[i] + i, i])
		arr = sorted(arr, reverse=True)
		temp = [0] * n
		for i in range(k):
			temp[arr[i][1]] = 1
		c = 0
		ans = 0
		for i in range(len(a)):
			if temp[i] == 1:
				c += 1
			else:
				ans += a[i] + c
		print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	pre = [arr[0]]
	for i in range(1, n):
		pre.append(pre[-1] + arr[i])
	suf = [arr[-1]]
	for i in range(n - 2, -1, -1):
		suf.append(suf[-1] + arr[i])
	suf = suf[::-1]
	fin = []
	for i in range(n):
		(idx, res) = (i, 0)
		if i != n - 1:
			res += n - i - 1 + suf[i + 1]
		if i > 0:
			res += pre[i - 1]
		fin.append([res, idx])
	fin.sort()
	if k == n:
		print(0)
	else:
		st = set()
		for i in range(k, n):
			st.add(fin[i][1])
		udhar = 0
		curr = 0
		for i in range(n):
			if i in st:
				curr += arr[i]
				curr += udhar
			else:
				udhar += 1
		print(curr)