Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Nikki has $N$ coconuts, she wants to prepare a special coconut soup for her best friend Mansi. In order to make this soup, she has to break $Z$ coconuts. For each coconut, there is a fixed number of times Nikki needs to hit it if she wants it to break. Nikki can only hit one coconut at the same time.

Their friend Sakshi is a troublemaker. This time, Sakshi shuffled the coconuts in some (unknown) way. You are given a sequence $A_{1}, A_{2}, \ldots, A_{N}$ with the following meaning: it is possible to label the coconuts $1$ through $N$ in such a way that for each valid $i$, the $i$-th coconut needs to be hit exactly $A_{i}$ times to break.

Nikki wants to prepare the soup as soon as possible, so she wants to minimise the number of times she has to hit coconuts in the worst case in order to break $Z$ coconuts. Formally, she wants to find a strategy of hitting coconuts, possibly depending on which coconuts broke after which hits, such that no matter which coconuts broke and when, it is guaranteed that after $H$ hits, there will be $Z$ broken coconuts, and there is no strategy with smaller $H$. Help Nikki find $H$ — the minimum required number of hits.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $Z$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------  Output ------
For each test case, print a single line containing one integer — the minimum required number of hits.

------  Constraints ------
$1 ≤ T ≤ 1,000$
$1 ≤  Z ≤ N ≤ 10^{3}$
$1 ≤ A_{i} ≤ 10^{6}$ for each valid $i$
the sum of $N \cdot Z$ over all test cases does not exceed $3 \cdot 10^{6}$

------  Subtasks ------
Subtask #1 (10 points):
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 500$
$Z = 1$
$1 ≤ A_{i} ≤ 1,000$ for each valid $i$
the sum of $N \cdot Z$ over all test cases does not exceed $3,000$

Subtask #2 (90 points): original constraints

----- Sample Input 1 ------ 
2
2 1
50 55 
2 1
40 100
----- Sample Output 1 ------ 
55
80
----- explanation 1 ------ 
Example case 1: Nikki can choose one coconut and try to hit it $55$ times. It will break either after the $50$-th hit or after the $55$-th hit.

Example case 2: Nikki can choose one coconut and hit it $40$ times. If it does not break, the other coconut must be the one that takes $40$ hits to break, so she should hit the other coconut $40$ times. In total, she needs to hit coconuts at most $80$ times.

Difficulty: VERY_HARD
Tags: Geometry

Dynamic programming

Sweep line algorithms
Skill types: Dynamic programming

Starter code:

Solutions:
import sys
sys.setrecursionlimit(10000)

def solve(arr, N, Z):
	if Z == 0:
		return 0
	cur = best = sum(arr[-Z:])
	for i in range(1, N - Z + 1):
		cur -= i * (arr[-i] - arr[-i - 1])
		cur += arr[-i - Z]
		if cur < best:
			best = cur
	if Z > 1:
		alternative = arr[0] * N + solve([x - arr[0] for x in arr[1:]], N - 1, Z - 1)
		if alternative < best:
			best = alternative
	return best
for _ in range(int(input())):
	(N, Z) = map(int, input().split())
	A = sorted(map(int, input().split()))
	print(solve(A, N, Z))


from sys import stdin, stdout
inf = 1000000000000007

def solve(n, z):
	dp = [[inf for j in range(n)] for i in range(z + 1)]
	a = []
	a = [int(i) for i in stdin.readline().split()]
	a.sort(reverse=True)
	cv_hullx = [[] for j in range(z + 1)]
	cv_hully = [[] for j in range(z + 1)]
	for i in range(n):
		for j in range(1, z + 1):
			if j == 1:
				dp[j][i] = (i + 1) * a[i]
			elif i >= j - 1:
				k = len(cv_hullx[j - 1])
				while k >= 2 and cv_hully[j - 1][k - 1] - cv_hully[j - 1][k - 2] >= (cv_hullx[j - 1][k - 1] - cv_hullx[j - 1][k - 2]) * a[i]:
					k -= 1
					cv_hullx[j - 1].pop()
					cv_hully[j - 1].pop()
				dp[j][i] = cv_hully[j - 1][k - 1] + (i - cv_hullx[j - 1][k - 1]) * a[i]
		for j in range(1, z + 1):
			if i >= j - 1:
				k = len(cv_hullx[j])
				while k >= 2 and (cv_hully[j][k - 1] - cv_hully[j][k - 2]) * (i - cv_hullx[j][k - 1]) >= (dp[j][i] - cv_hully[j][k - 1]) * (cv_hullx[j][k - 1] - cv_hullx[j][k - 2]):
					k -= 1
					cv_hullx[j].pop()
					cv_hully[j].pop()
				cv_hullx[j].append(i)
				cv_hully[j].append(dp[j][i])
	return min(dp[z])
for t in range(int(stdin.readline())):
	(n, z) = [int(i) for i in stdin.readline().split()]
	print(solve(n, z))


def solve(line1, line2):
	(m1, c1) = line1
	(m2, c2) = line2
	return (c2 - c1) / (m1 - m2)

def find(A, Z):
	N = len(A)
	A = [10 ** 10] + sorted(A)[::-1]
	dp = [[10 ** 10 for j in range(Z + 1)] for k in range(N + 1)]
	for i in range(1, N + 1):
		dp[i][1] = i * A[i]
	from collections import deque
	for z in range(2, Z + 1):
		temp = 10 ** 10
		intersections = [0]
		lines = [(-(z - 1), dp[z - 1][z - 1])]
		for k in range(z, N + 1):
			line = (-k, dp[k][z - 1])
			while intersections:
				if intersections[-1] > A[k]:
					intersections.pop()
					lines.pop()
				else:
					break
			(m0, c0) = lines[-1]
			ans = m0 * A[k] + c0
			dp[k][z] = ans + k * A[k]
			if line[0] * A[k] + line[1] >= ans:
				continue
			while lines:
				inter = solve(lines[-1], line)
				(m, c) = line
				(m0, c0) = lines[-1]
				pos = intersections[-1]
				if inter < pos and m * pos + c < m0 * pos + c0:
					lines.pop()
					intersections.pop()
				else:
					break
			lines += [line]
			intersections += [max(inter, 0)]
	return min([dp[i][Z] for i in range(1, N + 1)])
for _ in range(int(input())):
	(N, Z) = list(map(int, input().strip().split(' ')))
	A = list(map(int, input().strip().split(' ')))
	print(find(A, Z))


for _ in range(int(input())):
	(n, z) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	l1 = []
	c = 0
	q = l[:]
	for j in range(z, 0, -1):
		temp = []
		for i in range(len(q) - j + 1):
			temp.append((i + 1) * q[i] + sum(q[i + 1:i + j]))
		l1.append(min(temp) + c)
		c += len(q) * q[-1]
		q = [x - q[-1] for x in q]
		j = -1
		del q[-1]
	print(min(l1))


for t in range(int(input())):
	(n, z) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort()
	b = []
	for x in a:
		b.append(x)
	for i in range(1, n):
		b[i] += b[i - 1]
	if z == n:
		print(b[n - 1])
		continue
	c = [-1] * n
	i = n - z
	while i > 0:
		c[i] = b[i + z - 1] - b[i - 1] + (n - z - i) * a[i + z - 1]
		i -= 1
	c[0] = b[z - 1] + (n - z) * a[z - 1]
	min_v = c[0]
	for x in c:
		if min_v > x and x != -1:
			min_v = x
	sum_v = 0
	for j in range(1, z + 1):
		c = [-1] * n
		sum_v += b[j - 1] * (n + 1 - j)
		i = j
		k = 2
		while i < n:
			b[i] -= k * b[j - 1]
			a[i] -= b[j - 1]
			i += 1
			k += 1
		a[j - 1] = 0
		b[j - 1] = 0
		i = n - z + j
		while i > 0:
			if i < n:
				c[i] = b[i + z - j - 1] - b[i - 1] + (n - z + j - i) * a[i + z - j - 1]
			i -= 1
		i = j
		while i < n:
			if min_v > c[i] + sum_v and c[i] != -1:
				min_v = c[i] + sum_v
			i += 1
	print(min_v)


t = int(input())
maxi = 10 ** 18
import sys
sys.setrecursionlimit(10000)

def cal(low, high):
	score = maxi
	index = -maxi
	num = -maxi
	for i in range(low, high + 1):
		temp = l[i] * (high - (i - 1))
		if temp < score:
			index = i
			score = temp
			num = high - i
	return [score, index, num]

def find():
	index = 0
	num = 0
	score = maxi
	for i in range(len(mat)):
		if mat[i][0] == score and mat[i][2] > num:
			num = mat[i][2]
			index = i
		elif mat[i][0] < score:
			num = mat[i][2]
			score = mat[i][0]
			index = i
	return index

def altans(low, high, z):
	if z == 0:
		return maxi
	else:
		la = 0
		s = sum(rev_l[:z])
		out = s
		for i in range(low, high - z + 1):
			s += rev_l[(i + z) % n]
			s -= rev_l[i % n]
			la += 1
			score = s + rev_l[(i + 1) % n] * la
			out = min(out, score)
		for i in range(low, high):
			rev_l[i] -= rev_l[high]
		ans = min(out, rev_l[high] * (high - low + 1) + altans(low, high - 1, z - 1))
		return ans
for tcases in range(t):
	(n, z) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	rev_l = l[::-1]
	v = [[0, n - 1]]
	h = 0
	for zz in range(z):
		mat = []
		for i in range(len(v)):
			temp = cal(v[i][0], v[i][1])
			temp.append(i)
			mat.append(temp)
		k = find()
		if mat[k][0] == maxi:
			mat[k][0] = 0
			break
		else:
			h += mat[k][0]
			l1 = v[mat[k][3]][0]
			l2 = mat[k][1] + 1
			h1 = mat[k][1] - 1
			h2 = v[mat[k][3]][1]
			del v[mat[k][3]]
			if h1 >= l1:
				v.append([l1, h1])
			if h2 >= l2:
				v.append([l2, h2])
				for i in range(l2, h2 + 1):
					l[i] -= l[mat[k][1]]
	alth = altans(0, n - 1, z)
	fans = min(h, alth)
	print(fans)


def get_input_line():
	return input()

def solve_small(numbers, n, _):
	sorted_numbers = sorted(numbers)
	factors = [i for i in range(n, 0, -1)]
	return min([n * f for (n, f) in zip(sorted_numbers, factors)])

def solve_med(numbers, n, z):
	if z == n:
		return sum(numbers)
	sorted_numbers = sorted(numbers)
	partial_sums = [sum(sorted_numbers[:z])]
	for i in range(1, n - z + 1):
		prev_sum = partial_sums[-1]
		curr_sum = prev_sum - sorted_numbers[i - 1] + sorted_numbers[i + z - 1]
		partial_sums.append(curr_sum)
	min_sum = 0
	for i in range(n - z + 1):
		total_sum = partial_sums[i] + sorted_numbers[i + z - 1] * (n - z - i)
		if not min_sum or total_sum < min_sum:
			min_sum = total_sum
	for n_ in range(n, z - 1, -1):
		for i in range(z, -1, -1):
			left = i
			right = z - i
			between = n_ - z
			if left == 0:
				between = 0
			left_sum = sum(sorted_numbers[:left])
			right_sum = sum(sorted_numbers[n_ - right:n_])
			between_sum = between * sorted_numbers[i - 1]
			extra_sum = (n - n_) * sorted_numbers[n_ - 1]
			total_sum = left_sum + between_sum + right_sum + extra_sum
			min_sum = min(min_sum, total_sum)
	return min_sum

def solve_big(numbers, n, z):
	sorted_numbers = sorted(numbers)
	min_sum = 0
	prev_partial_sum = sum(sorted_numbers[:z])
	curr_partial_sum = prev_partial_sum
	for i in range(n - z + 1):
		right = sorted_numbers[i + z - 1]
		multiplier = n - z - i
		if i > 0:
			prev_partial_sum = curr_partial_sum
			curr_partial_sum = prev_partial_sum - sorted_numbers[i - 1] + sorted_numbers[i + z - 1]
		curr_sum = curr_partial_sum + right * multiplier
		if not min_sum or curr_sum < min_sum:
			min_sum = curr_sum
	reverse_partial_sum = [0] * n
	for i in range(n - 1, -1, -1):
		reverse_partial_sum[i] = sorted_numbers[i]
		if i < n - 1:
			reverse_partial_sum[i] += reverse_partial_sum[i + 1]
	for n_ in range(z, n + 1):
		for i in range(z, -1, -1):
			left = i
			right = z - i
			between = n_ - z
			if left == 0:
				between = 0
			left_sum = reverse_partial_sum[0]
			if left < n:
				left_sum -= reverse_partial_sum[left]
			right_sum = 0
			if n_ - right < n:
				right_sum = reverse_partial_sum[n_ - right]
				if n_ < n:
					right_sum -= reverse_partial_sum[n_]
			between_sum = between * sorted_numbers[i - 1]
			extra_sum = (n - n_) * sorted_numbers[n_ - 1]
			total_sum = left_sum + between_sum + right_sum + extra_sum
			min_sum = min(min_sum, total_sum)
	return min_sum

def main():
	t = int(get_input_line())
	for i in range(t):
		(n, z) = map(int, get_input_line().split())
		numbers = list(map(int, get_input_line().split()))
		result = solve_big(numbers, n, z)
		print(result)

def _check_differences(n, z, tests=1000):
	import random
	for i in range(tests):
		numbers = [random.randint(1, 10) for _ in range(n)]
		rs = solve_big(numbers, n, z)
		rb = solve_med(numbers, n, z)
		if rs != rb:
			print(n, z)
			print(sorted(numbers), rs, rb)
			exit()

def _check_performance(n, z, tests=1000):
	import random
	import time
	all_numbers = []
	for i in range(tests):
		numbers = [random.randint(1, 10) for _ in range(n)]
		all_numbers.append(numbers)
	t1 = time.time()
	all_rs = []
	for i in range(tests):
		rs = solve_big(all_numbers[i], n, z)
		all_rs.append(rs)
	t2 = time.time()
	all_rb = []
	for i in range(tests):
		rb = solve_med(all_numbers[i], n, z)
		all_rb.append(rb)
	t3 = time.time()
	for (numbers, rs, rb) in zip(all_numbers, all_rs, all_rb):
		if rs != rb:
			print(sorted(numbers), rs, rb)
			exit()
	print('rs: {}, rb: {}'.format(t2 - t1, t3 - t2))
main()


T = int(input())
while T > 0:
	T -= 1
	(N, Z) = map(int, input().split())
	S = list(map(int, input().split()))
	S.sort(reverse=True)
	answer = []
	steps = 0
	Q = S[:]
	for j in range(Z, 0, -1):
		TempSubAns = []
		for i in range(len(Q) - j + 1):
			TempSubAns.append((i + 1) * Q[i] + sum(Q[i + 1:i + j]))
		answer.append(min(TempSubAns) + steps)
		steps += len(Q) * Q[-1]
		Q = [x - Q[-1] for x in Q]
		j = -1
		del Q[-1]
	print(min(answer))


t = int(input())
for _ in range(t):
	(n, z) = map(int, input().split())
	a = list(map(int, input().split()))
	a = sorted(a)
	ans = 1 << 64
	p = [0] * (n + 1)
	for i in range(1, n + 1):
		p[i] = p[i - 1] + a[i - 1]
	ans1 = 1 << 64
	i = 0
	while i + z - 1 < n:
		ending = i + z - 1
		currAns = 0
		currAns += p[ending + 1] - p[i]
		currAns += a[ending] * (n - ending - 1)
		ans1 = min(ans1, currAns)
		i += 1
	ans = min(ans, ans1)
	ans1 = 1 << 64
	for i in range(z - 1, n):
		x = 1
		y = z - 1
		while y > 0 and x < z:
			currAns = 0
			currAns += p[x]
			currAns += a[x - 1] * (i - y + 1 - x)
			currAns += p[i + 1] - p[i - y + 1]
			currAns += a[i] * (n - i - 1)
			ans1 = min(currAns, ans1)
			x = x + 1
			y = y - 1
	ans = min(ans, ans1)
	print(ans)


import sys
sys.setrecursionlimit(10 ** 9)

def rec(arr, z, score, ans):
	if z == 0:
		return ans
	summ = 0
	for i in range(z):
		summ += arr[i]
	minTemp = summ + score
	for i in range(z, len(arr)):
		summ = summ - arr[i - z] + arr[i]
		temp = score + summ + arr[i - z + 1] * (i - z + 1)
		if temp < minTemp:
			minTemp = temp
	length = len(arr)
	a = arr.pop(length - 1)
	for i in range(len(arr)):
		arr[i] -= a
	z -= 1
	if minTemp < ans:
		ans = minTemp
	return rec(arr, z, a * length + score, ans)
t = int(input())
for r in range(t):
	(n, z) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	print(rec(l, z, 0, 99999999999999999))