Read problems statements in [Mandarin Chinese], [Russian], and [Bengali] as well.

You are given an array A of N elements. You can do the following operations on that array:

Remove the leftmost element of the array, with index l, for the cost A_{l}. This can be done any number of times if the array is non-empty (has at least 1 element).
Remove the rightmost element of the array, with index r, for the cost A_{r}. This can be done any number of times if the array is non-empty (has at least 1 element).
Remove both the leftmost and rightmost element, with indexes l and r respectively, for a fixed cost X which is given. This operation can only be done K times and only if the array has at least 2 elements left.

If the array has only 1 element left, then the rightmost element is the same as the leftmost element so the first and second operations will have the same cost.

You have to print the minimum cost to *clear the array* (remove all elements using one of the three operations above).

NOTE: The answer may not fit in 32-bit integers, so please use 64-bit data types in your programming language.

------ Input Format ------ 

- The first line of the input contains T - the number of test cases. Then the test cases follow.

- Each test case contains 2 lines of input.

- The first line of each test case contains three integers: N, K, and X separated by spaces.

- The second line of each test case contains N space-separated positive integers, A_{1},A_{2},\ldots A_{N}.

------ Output Format ------ 

For each test case, output on one line the minimum cost to clear the array.

------ Constraints ------ 

$1 ≤ T ≤ 200$
$1 ≤ N ≤ 5000$
$0 ≤ K ≤ \lfloor \frac{N}{2} \rfloor$
$1 ≤ X ≤ 10^{9}$
$1 ≤ A_{i} ≤ 10^{9}$

----- Sample Input 1 ------ 
3
5 2 7
9 10 11 12 13
5 0 7
9 9 9 9 9
5 2 7
9 1 2 3 10

----- Sample Output 1 ------ 
23
45
13

----- explanation 1 ------ 
For the first test case, we can remove $A_{1}$ for cost $9$, which makes the array $[10, 11, 12, 13]$. Then we can do the third operation to remove $10$ and $13$ for cost $7$, which makes the array $[11, 12]$. We can again do the third operation to remove $11$ and $12$ for cost $7$ which clears the array.

The total cost is therefore $23$, which is the minimum cost possible.

Difficulty: HARD
Tags: Sorting

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	l.reverse()
	(i, j) = (0, 1)
	(cs, ans) = (sum(l), sum(l))
	while k > 0:
		p = l[i] + l[i + 1]
		cs -= p
		if j * x + cs < ans:
			ans = j * x + cs
		i += 2
		j += 1
		k -= 1
	print(ans)


t = int(input())
for i in range(t):
	(n, k, x) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	j = 0
	s = 0
	while j < n:
		if k == 0:
			break
		if j + 1 < n:
			a = l[j] + l[j + 1]
			if a > x:
				s += x
				j += 2
				k -= 1
			else:
				break
	z = l[j:]
	s += sum(z)
	print(s)


t = int(input())
for i in range(t):
	(n, k, x) = map(int, input().split())
	lis = list(map(int, input().split()))
	lis.sort(reverse=True)
	j = 0
	sumi = 0
	while j < n:
		if k == 0:
			break
		if j + 1 < n:
			temp = lis[j] + lis[j + 1]
			if temp > x:
				sumi += x
				j += 2
				k = k - 1
			else:
				break
	z = lis[j:]
	sumi += sum(z)
	print(sumi)


import math
for q in range(int(input())):
	(n, k, x) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort()
	sum1 = 0
	index = -1
	for i in range(n - 1):
		if a[i] + a[i + 1] > x and i > n - 2 * k - 1:
			index = i
			break
		sum1 += a[i]
		if i == n - 2:
			sum1 += a[i + 1]
	if index != -1:
		temp = n - index
		if temp % 2 == 0:
			sum1 += x * (temp // 2)
		elif index == n - 1:
			sum1 += a[index]
		else:
			sum1 += a[index]
			sum1 += x * (temp // 2)
	print(sum1)


for _ in range(int(input())):
	(N, K, X) = map(int, input().split())
	A = list(map(int, input().split()))
	cost = 0
	done = 1
	A.sort()
	while len(A) > 2 * K:
		cost += A[0]
		A.pop(0)
	if K == 0:
		print(cost)
	else:
		while A:
			if A[0] + A[1] < X:
				cost += A[0] + A[1]
				A.pop(0)
				A.pop(0)
			else:
				cost += X
				A.pop(0)
				A.pop(0)
		print(cost)


for i in range(int(input())):
	(n, k, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=1)
	i = 0
	ans = 0
	while i + 1 < n and a[i] + a[i + 1] > x and (k > 0):
		ans += x
		i += 2
		k -= 1
		if k == 0:
			break
	if i == n:
		print(ans)
	else:
		print(ans + sum(a[i:]))


t = int(input())
for i in range(t):
	(n, k, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a = sorted(a)
	ans = 0
	while k and len(a) > 1 and (a[-1] + a[-2] > x):
		ans += x
		k -= 1
		a.pop(-1)
		a.pop(-1)
	ans += sum(a)
	print(ans)


from sys import stdin
from collections import deque
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 6)

def solve(n, k, x, nums):
	nums.sort()
	pair = []
	result = 0
	while nums:
		pair.append(nums.pop())
		if len(pair) == 2 and sum(pair) >= x and (k > 0):
			k -= 1
			result += x
			pair = []
	result = result + sum(pair) + sum(nums)
	print(result)
input = stdin.readline
ln = int(input())
for _ in range(ln):
	(n, k, x) = map(int, input().split())
	nums = list(map(int, input().split()))
	solve(n, k, x, nums)


for _ in range(int(input())):
	(n, k, v) = map(int, input().split())
	a = [int(i) for i in input().split()]
	a = sorted(a)
	ans = 0
	while k and len(a) > 1 and (a[-1] + a[-2] > v):
		ans += v
		k -= 1
		a.pop(-1)
		a.pop(-1)
	ans += sum(a)
	print(ans)


def mincost(k, l):
	n = k[0]
	t = k[1]
	x = k[2]
	cost = 0
	l = sorted(l)
	c = 0
	i = n - 1
	while c == 0 and i >= 1:
		if l[i] + l[i - 1] >= x and t != 0:
			cost += x
			t = t - 1
			i = i - 2
		else:
			c += 1
	if i == -1:
		return cost
	for m in range(i + 1):
		cost += l[m]
	return cost
t = int(input())
for i in range(t):
	k = list(map(int, input().split()))
	l = list(map(int, input().split()))
	print(mincost(k, l))


t = int(input())
for i in range(t):
	(n, k, x) = map(int, input().split())
	numbers = [int(x) for x in input().split()]
	numbers.sort(reverse=True)
	minCost = 0
	for j in range(k):
		if len(numbers) >= 2:
			first = numbers[0]
			second = numbers[1]
			s = first + second
			if x < s:
				minCost += x
				numbers.remove(first)
				numbers.remove(second)
			else:
				break
		else:
			break
	minCost += sum(numbers)
	print(minCost)


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


test = int(input())
for t in range(test):
	(n, k, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr = sorted(arr, reverse=True)
	i = 0
	sm = 0
	while k > 0 and i < n - 1:
		if arr[i] + arr[i + 1] < x:
			break
		sm += x
		i += 2
		k -= 1
	print(sm + sum(arr[i:]))


T = int(input())
for t in range(T):
	(n, k, x) = [int(i) for i in str(input()).split()]
	arr = [int(i) for i in str(input()).split()]
	arr = sorted(arr, reverse=True)
	final = 0
	idx = 0
	while True:
		if arr[idx] + arr[idx + 1] > x and k > 0:
			final += x
			k -= 1
			idx += 2
		else:
			final += arr[idx] + arr[idx + 1]
			idx += 2
		if idx == len(arr):
			break
		if idx == len(arr) - 1:
			final += arr[idx]
			break
	print(final)


t = int(input())
for _ in range(t):
	(N, K, X) = [int(x) for x in input().split()]
	sequence = [int(x) for x in input().split()]
	sequence.sort()
	cost = sum(sequence[0:N - 2 * K])
	if K > 0:
		for i in range(N - 2 * K, N, 2):
			total = sequence[i] + sequence[i + 1]
			cost += min(total, X)
	else:
		cost += sum(sequence[N - 2 * K:])
	print(cost)


for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	clear = [0]
	clear.extend(sorted(list(map(int, input().split()))))
	count = 0
	while n - 1 >= 0:
		if clear[n] + clear[n - 1] > x and k != 0:
			count += x
			k -= 1
			n -= 2
		else:
			count += clear[n]
			n -= 1
	print(count)


from queue import PriorityQueue
t = int(input())
while t:
	(n, k, x) = map(int, input().split())
	a = []
	pq = PriorityQueue()
	ans = 0
	for j in input().split():
		j = int(j)
		a.append(j)
		pq.put(-1 * j)
	while k and pq.qsize() > 1:
		k -= 1
		c = -1 * pq.get()
		d = -1 * pq.get()
		if c + d < x:
			pq.put(-1 * c)
			pq.put(-1 * d)
			break
		ans += x
	while not pq.empty():
		z = -1 * pq.get()
		ans += z
	print(ans)
	t -= 1


t = int(input())
while t:
	(N, K, X) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	count = 0
	arr.sort()
	n = N
	if N == 0:
		print(0)
	if N == 1:
		print(arr[0])
	while K > 0 and len(arr) > 1:
		sz = len(arr)
		if X < arr[sz - 1] + arr[sz - 2]:
			arr.pop()
			arr.pop()
			count += X
			K -= 1
		else:
			break
	for i in range(len(arr)):
		count += arr[i]
	print(count)
	t -= 1


from collections import deque
t = int(input())
for _ in range(0, t):
	(n, k, x) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	a = deque(a)
	if len(a) == 1:
		print(a[0])
		continue
	if k == 0:
		print(sum(a))
		continue
	s = 0
	for i in range(0, k):
		if len(a) <= 1:
			break
		if a[0] + a[1] > x:
			s += x
			a.popleft()
			a.popleft()
		else:
			break
	s += sum(a)
	print(s)


t = int(input())
for tt in range(t):
	(n, k, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	i = n - 1
	result = 0
	for j in range(k):
		if arr[i] + arr[i - 1] >= x:
			result += x
			i -= 2
		else:
			break
	while i >= 0:
		result += arr[i]
		i -= 1
	print(result)


for _ in range(int(input())):
	(n, k, x) = map(int, input().strip().split())
	l = list(map(int, input().strip().split()))
	if k == 0:
		print(sum(l))
		continue
	l.sort()
	ll = l[-2 * k:]
	total = sum(l[:-2 * k])
	for i in range(0, len(ll) - 1, 2):
		if ll[i] + ll[i + 1] < x:
			total += ll[i] + ll[i + 1]
		else:
			total += x
	print(total)


for _ in range(int(input())):
	(n, k, x) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	l.sort()
	cost = 0
	a = len(l)
	d = a - 2 * k
	i = 0
	while i < a:
		if i < d:
			cost += l[i]
			i += 1
		elif l[i] + l[i + 1] < x:
			cost += l[i] + l[i + 1]
			i += 2
			k -= 1
		else:
			cost += x * k
			break
	print(cost)


for i in range(int(input())):
	(n, k, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	ans = 0
	pos = -1
	for j in range(0, n - 1, 2):
		if k == 0:
			break
		s1 = a[j] + a[j + 1]
		ans += min(s1, x)
		k -= 1
		pos = j + 1
	for j in range(pos + 1, n):
		ans += a[j]
	print(ans)


for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	l = sorted(list(map(int, input().split())), reverse=True)
	cost = i = 0
	while True:
		if i == len(l) - 1:
			cost += l[i]
			break
		elif i >= len(l):
			break
		elif l[i] + l[i + 1] > x and k > 0:
			cost += x
			k -= 1
		elif l[i] + l[i + 1] <= x or k == 0:
			cost += l[i] + l[i + 1]
		i += 2
	print(cost)


import collections
for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	li = list(map(int, input().split()))
	li.sort(reverse=True)
	ans = 0
	dq = collections.deque(li)
	for i in range(k):
		if len(dq) < 2:
			break
		a = dq.popleft()
		b = dq.popleft()
		if a + b < x:
			ans += a + b
			break
		ans += x
	print(sum(dq) + ans)


for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	arr = sorted(list(map(int, input().split())))
	s = 0
	for i in range(n):
		if i == n - 2 * k:
			break
		s += arr[i]
	else:
		i += 1
	print(sum([min(x, arr[i] + arr[i + 1]) for i in range(i, n, 2)]) + s)


for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	s = 0
	for i in range(n):
		if i == n - 2 * k:
			break
		s += arr[i]
	else:
		i += 1
	pairDel = 0
	for i in range(i, n, 2):
		if arr[i] + arr[i + 1] > x:
			pairDel += x
		else:
			pairDel += arr[i] + arr[i + 1]
	print(pairDel + s)


for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	ans = 0
	while len(arr) >= 2 and arr[-1] + arr[-2] >= x and (k > 0):
		arr.pop()
		arr.pop()
		ans += x
		k -= 1
	ans += sum(arr)
	print(ans)


def solution(arr, k, x):
	if k == 0:
		return sum(arr)
	min_cost = 0
	for i in range(k):
		if len(arr) < 2:
			return sum(arr) + min_cost
		S = arr[-1]
		arr.pop()
		S += arr[-1]
		arr.pop()
		if S < x:
			return min_cost + S + sum(arr)
		min_cost += x
	return min_cost + sum(arr)
for i in range(int(input())):
	(n, k, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	print(solution(arr, k, x))


for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	d = dict()
	l = [int(i) for i in input().split()]
	l = sorted(l)
	ans = 0
	while len(l) > 1:
		f = 0
		if len(l) > 1 and l[-1] + l[-2] > x and k:
			ans += x
			f = 1
			l = l[:-2]
			k -= 1
		if f == 0:
			ans += l[-1]
			l = l[:-1]
	print(ans + sum(l))


def solveF(N, K, X, A):
	A.sort()
	index = 0
	single_remove = len(A) - 2 * K
	cost = 0
	while index < single_remove:
		cost += A[index]
		index += 1
	if (len(A) - index) % 2:
		cost += A[index]
		index += 1
	while index <= N - 2 and A[index] + A[index + 1] < X:
		cost += A[index] + A[index + 1]
		index += 2
	cost += X * (len(A) - index) // 2
	return cost
for _ in range(int(input())):
	(N, K, X) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	print(solveF(N, K, X, A))


t = int(input())
for _ in range(t):
	(n, k, x) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	ans = 0
	a = sorted(arr)
	ind = len(a) - 1
	while k > 0 and len(a) > 1:
		m = len(a)
		sum1 = a[m - 1] + a[m - 2]
		if x <= sum1:
			a.pop(m - 1)
			a.pop(m - 2)
			ans += x
			k -= 1
		else:
			break
	ans += sum(a[:])
	print(ans)


def clearArr(arr, n, k, x):
	sumi = sum(arr)
	if k == 0:
		return sumi
	arr.sort(reverse=True)
	prs = []
	i = 0
	while i + 1 < n and k:
		if arr[i] + arr[i + 1] > x:
			prs.append(arr[i])
			prs.append(arr[i + 1])
			k -= 1
		i += 2
	suma = sum(prs)
	le = len(prs)
	return sumi - suma + x * (le // 2)
for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	print(clearArr(arr, n, k, x))


t = int(input())
for _ in range(t):
	(n, k, x) = map(int, input().split())
	l = list(map(int, input().split()))
	if k == 0:
		print(sum(l))
		continue
	l = sorted(l, reverse=True)
	ans = 0
	i = 0
	while i < len(l) - 1 and k > 0:
		if l[i] + l[i + 1] > x:
			ans += x
			l[i] = 0
			l[i + 1] = 0
			i += 2
			k -= 1
		else:
			break
	ans += sum(l)
	print(ans)


import heapq
for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	a = list(map(int, input().split()))
	ls = []
	heapq.heapify(ls)
	for i in a:
		heapq.heappush(ls, -1 * i)
	ans = 0
	for i in range(k):
		p = -1 * heapq.heappop(ls)
		q = -1 * heapq.heappop(ls)
		if q + p < x:
			ans += p + q
			break
		ans += x
	for i in ls:
		ans += -1 * i
	print(ans)


for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	cost = sum(arr[:n - 2 * k])
	arr = arr[n - 2 * k:]
	for i in range(k):
		cost += min(arr[2 * i] + arr[2 * i + 1], x)
	print(cost)


for __ in range(int(input())):
	(N, K, X) = map(int, input().split())
	A = list(map(int, input().split()))
	cost = sum(A)
	A.sort(reverse=True)
	for i in range(0, 2 * K, 2):
		if X <= A[i] + A[i + 1]:
			cost += X - (A[i] + A[i + 1])
	print(cost)


t = int(input())
for _ in range(t):
	(n, k, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	cost = 0
	i = 0
	while k > 0 and len(a) > 1:
		i = len(a)
		if a[i - 1] + a[i - 2] >= x:
			cost += x
			a.pop(-1)
			a.pop(-1)
			k -= 1
		else:
			break
	cost += sum(a)
	print(cost)


for tc in range(int(input())):
	ls = list(map(int, input().split()))
	lk = list(map(int, input().split()))
	lk.sort(reverse=True)
	val = ls[2]
	k = ls[1]
	su = 0
	for x in range(0, len(lk) - 1, 2):
		if k > 0:
			if lk[x] + lk[x + 1] > val:
				su += val
				k -= 1
			else:
				su += lk[x] + lk[x + 1]
		else:
			su += lk[x] + lk[x + 1]
	if len(lk) % 2 == 1:
		su += lk[-1]
	print(su)


import heapq
t = int(input())
for _ in range(t):
	(n, k, x) = map(int, input().split())
	t = k
	nos = list(map(int, input().split()))
	q = []
	rems = []
	nos.sort(reverse=True)
	ans = sum(nos)
	for i in range(0, 2 * k, 2):
		if nos[i] + nos[i + 1] > x:
			ans += x - nos[i] - nos[i + 1]
	print(ans)


for t in range(int(input())):
	(n, k, x) = map(int, input().split())
	A = [int(i) for i in input().split()]
	A.sort()
	res = 0
	while k > 0:
		res += min(x, A.pop() + A.pop())
		k -= 1
	while len(A) > 0:
		res += A.pop()
	print(res)


import sys

def yn(val):
	re = ['Yes', 'No']
	return re[val]

def Ajay():
	aj = chr(65) + chr(74) + chr(64) + chr(165)
	return aj

def main():
	(a, b, c) = map(int, sys.stdin.readline().split())
	arr = list(map(int, input().split()))
	if b == 0:
		return sum(arr)
	arr.sort(reverse=True)
	ans = 0
	for i in range(0, b * 2, 2):
		if i + 1 < a:
			ans += min(c, arr[i] + arr[i + 1])
	ans += sum(arr[b * 2:])
	return ans
t = int(sys.stdin.readline())
for _ in range(t):
	print(main())


t = int(input())
for _ in range(t):
	(n, k, x) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	s = 0
	sss = 0
	for i in range(0, 2 * k, 2):
		sss += l[i] + l[i + 1]
		if l[i] + l[i + 1] > x:
			s += x
		else:
			sss -= l[i] + l[i + 1]
			break
	ss = sum(l)
	print(ss - sss + s)


def solve():
	(n, k, x) = [int(i) for i in input().split(' ')]
	arr = [int(i) for i in input().split(' ')]
	arr.sort(reverse=True)
	sol = 0
	for i in range(0, n, 2):
		if k <= 0:
			ind = i
			break
		if arr[i] + arr[i + 1] > x:
			sol += x
			k -= 1
			ind = i + 2
		else:
			ind = i
			break
	sol += sum(arr[ind:])
	print(sol)
	return
t = int(input())
for tests in range(t):
	solve()


t = int(input())
for _ in range(t):
	(n, k, x) = [int(i) for i in input().split()]
	l = [int(i) for i in input().split()]
	l.sort(reverse=True)
	(i, s) = (0, 0)
	while i < n - 1 and k != 0:
		if l[i] > x:
			s += x
			k -= 1
			i += 2
		elif l[i] + l[i + 1] > x:
			s += x
			k -= 1
			i += 2
		else:
			break
	s += sum(l[i:])
	print(s)


def solve(array, k, sub):
	array.sort()
	cost = 0
	index = len(array) - 1
	while index >= 0:
		if k > 0 and index > 0 and (sub <= array[index] + array[index - 1]):
			cost += sub
			index -= 2
			k -= 1
		else:
			cost += sum(array[:index + 1])
			break
	return cost
test = int(input())
for _ in range(test):
	(n, k, xx) = [int(x) for x in input().split()]
	array = [int(x) for x in input().split()]
	print(solve(array, k, xx))


T = int(input())
for t in range(T):
	(n, k, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	pair = 0
	ts = 0
	s = 0
	i = n - 1
	while pair < k and i >= 0:
		if arr[i] + arr[i - 1] >= x:
			s += x
			pair += 1
			i -= 2
		else:
			break
	rest = sum(arr[:i + 1])
	print(rest + s)


from collections import Counter
t = int(input())
while t:
	ans = 0
	(n, k, x) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = sum(l)
	l = sorted(l, reverse=1)
	for q in range(k):
		s = l[q * 2] + l[q * 2 + 1]
		if s > x:
			ans = ans - s + x
		else:
			break
	print(ans)
	t = t - 1


for i in range(int(input())):
	(n, k, x) = map(int, input().split())
	a = [int(j) for j in input().split()]
	a.sort(reverse=True)
	(ans, j) = (0, 0)
	while j < len(a):
		if j + 1 < len(a) and a[j] + a[j + 1] >= x and (k > 0):
			ans += x
			j += 2
			k -= 1
		else:
			ans += a[j]
			j += 1
	print(ans)


import sys
import math
from collections import defaultdict
mod = 1000000007
T = 1
T = int(sys.stdin.readline())
for _ in range(T):
	(n, k, x) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	s = 0
	pos = 0
	flg = 1
	for i in range(0, k):
		t = l[i << 1] + l[i << 1 | 1]
		if t <= x:
			pos = i << 1
			flg = 1
			break
		s += x
		flg = 0
	if flg == 0:
		pos = k << 1
	s += sum(l[pos:])
	print(s)


for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	cost = 0
	length = n
	while length:
		if length >= 2 and arr[-1] + arr[-2] >= x and (k > 0):
			length -= 2
			cost += x
			arr = arr[0:len(arr) - 2]
			k -= 1
		elif length >= 1:
			length -= 1
			cost += arr[-1]
			arr = arr[0:len(arr) - 1]
	print(cost)


def costClrArr(n, k, x, arr):
	totalCost = 0
	if n == 1:
		return arr[0]
	if n == 2:
		return min(x, arr[0] + arr[1])
	arr = arr[::-1]
	i = 0
	while k > 0:
		c = arr[i] + arr[i + 1]
		if x <= c:
			totalCost = totalCost + x
			k -= 1
			i += 2
		else:
			k = 0
	for idx in range(i, n):
		totalCost = totalCost + arr[idx]
	return totalCost
t = int(input())
for _ in range(t):
	(n, k, x) = map(int, input().strip().split(' '))
	arr = sorted(list(map(int, input().strip().split(' '))))
	print(costClrArr(n, k, x, arr))


t = int(input())
for test in range(t):
	(n, k, x) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort()
	i = n - 2
	j = n - 1
	res = 0
	while i >= 0:
		if a[i] + a[j] >= x and k > 0:
			res += x
			i -= 2
			j -= 2
			k -= 1
		else:
			res += a[i] + a[j]
			i -= 2
			j -= 2
	if j == 0:
		res += a[j]
	print(res)


import sys
import os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
depth = 1000005
mod = 1000000007
lim = mod * mod
sys.setrecursionlimit(depth)
from math import inf, ceil, sqrt
from collections import defaultdict
for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a = sorted(a, reverse=True)
	(ans, i) = (0, 1)
	while i < n and k and (a[i - 1] + a[i] >= x):
		ans += x
		k -= 1
		i += 2
	i -= 1
	while i < n:
		ans += a[i]
		i += 1
	print(ans)


import copy

def minimumcost(arr, n, k, x):
	sumi = sum(arr)
	arr.sort(reverse=True)
	if k == 0:
		return sumi
	prs = []
	i = 0
	while i < n and k:
		if arr[i] + arr[i + 1] > x:
			prs.append(arr[i])
			prs.append(arr[i + 1])
		k -= 1
		i += 2
	sumb = sum(prs)
	sumi = sumi - sumb + len(prs) * x // 2
	return sumi
for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	print(minimumcost(arr, n, k, x))


def prog_name():
	(n, k, const) = map(int, input().split())
	l = list(map(int, input().split()))
	if k == 0:
		print(sum(l))
	else:
		l.sort()
		cost = 0
		l.reverse()
		ind = 0
		while k > 0:
			k -= 1
			cost += min(l[ind] + l[ind + 1], const)
			ind += 2
		cost += sum(l[ind:])
		print(cost)
T = int(input())
for unique in range(T):
	prog_name()


import math
for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	a = list(map(int, input().split()))
	if k == 0:
		print(sum(a))
	else:
		a.sort(reverse=True)
		new1 = a[:2 * k]
		new = a[2 * k:]
		price = 0
		price += sum(new)
		for i in range(0, 2 * k, 2):
			price += min(new1[i] + new1[i + 1], x)
		print(price)


for t in range(int(input())):
	(N, K, X) = map(int, input().split())
	arr = list(map(int, input().split()))
	cost = 0
	i = N - 1
	arr.sort()
	while K:
		if arr[i] + arr[i - 1] > X:
			cost += X
			K -= 1
			i -= 2
		else:
			break
	cost += sum(arr[:i + 1])
	print(cost)


import sys
import math
import heapq
from collections import defaultdict as dd
from collections import OrderedDict as od
from collections import deque
from itertools import permutations as pp
from itertools import combinations as cc
from sys import stdin
from functools import cmp_to_key
from functools import lru_cache
from bisect import bisect_left as bs_l
from bisect import bisect_right as bs_r
input = sys.stdin.readline
mod = 10 ** 9 + 7
sys.setrecursionlimit(10 ** 5)
T = int(input())
for _ in range(T):
	(n, k, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	ans = 0
	c = 0
	for i in range(0, n - 1, 2):
		if k:
			xx = arr[i] + arr[i + 1]
			if x >= xx:
				break
			else:
				ans += x
				k -= 1
				c += 2
	for j in range(c, n):
		ans += arr[j]
	print(ans)


t = int(input())
for _ in range(t):
	(n, k, x) = map(int, input().split())
	a = list(map(int, input().split()))
	j = n - 1
	a.sort()
	j = n - 1
	ans = 0
	for i in range(k):
		q = a[j] + a[j - 1]
		if q < x:
			break
		else:
			ans += x
			j -= 2
	while j != -1:
		ans += a[j]
		j -= 1
	print(ans)


for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	cost = 0
	i = n - 1
	while k > 0 and i > 0:
		if a[i] + a[i - 1] >= x:
			k -= 1
			cost += x
		else:
			break
		i -= 2
	for j in range(0, i + 1):
		cost += a[j]
	print(cost)


import heapq
test = int(input())
for i in range(0, test):
	(n, k, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	for i in range(0, n):
		arr[i] = 0 - arr[i]
	heapq.heapify(arr)
	counter = 0
	for i in range(0, k):
		s = heapq.heappop(arr)
		t = heapq.heappop(arr)
		if abs(s) + abs(t) >= x:
			counter = counter + x
		else:
			counter = counter + abs(s) + abs(t)
	g = list(arr)
	for i in g:
		counter = counter + abs(i)
	print(counter)


for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	s = 0
	l = list(map(int, input().split()))
	l.sort()
	while k > 0 and len(l) > 1:
		if l[-1] + l[-2] > x:
			s += x
			k -= 1
			l.pop()
			l.pop()
		else:
			break
	s = sum(l) + s
	print(s)


for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	i = len(arr) - 1
	j = len(arr) - 2
	cost = 0
	if k == 0:
		print(sum(arr))
	else:
		while k > 0:
			if arr[i] + arr[j] > x:
				cost += x
			else:
				break
			i -= 2
			j -= 2
			k -= 1
		for i in range(i + 1):
			cost += arr[i]
		print(cost)


for _ in range(int(input())):
	(n, k, x) = map(int, input().split(' '))
	arr = [int(w) for w in input().split(' ')]
	arr.sort(reverse=True)
	ans = sum(arr)
	i = 0
	while i < n and i + 1 < n:
		if k == 0:
			break
		if arr[i] + arr[i + 1] > x:
			ans = ans - (arr[i] + arr[i + 1] - x)
			k = k - 1
		else:
			break
		if k == 0:
			break
		i = i + 2
	print(ans)


t = int(input())
for _ in range(t):
	(n, k, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	sum = 0
	arr.sort(reverse=True)
	pos = -1
	for j in range(0, n - 1, 2):
		if k == 0:
			break
		s = arr[j] + arr[j + 1]
		sum += min(s, x)
		k -= 1
		pos = j + 1
	for j in range(pos + 1, n):
		sum += arr[j]
	print(sum)


for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	flag = 1
	i = 0
	ans = 0
	while i < n:
		if i + 1 < n and k > 0 and flag:
			if a[i] + a[i + 1] > x:
				ans += x
				i += 2
				k -= 1
			else:
				flag = 0
				ans += a[i]
				i += 1
		else:
			ans += a[i]
			i += 1
	print(ans)


t = int(input())
for i in range(t):
	(n, k, x) = map(int, input().split())
	a = list(map(int, input().split()))
	c = sum(a)
	a.sort(reverse=True)
	t1 = 0
	r = 0
	while t1 == 0:
		if a[r] + a[r + 1] > x and k > 0:
			c = c - (a[r] + a[r + 1]) + x
			k = k - 1
			r = r + 2
		else:
			r = r + 1
		if k == 0:
			t1 == 1
			break
		if r >= n - 1:
			t1 == 1
			break
	print(c)


t = int(input())
for _ in range(t):
	(n, k, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	i = n - 1
	ans = 0
	while i >= 1 and k > 0:
		temp = arr[i] + arr[i - 1]
		if temp <= x:
			ans = ans + temp
		else:
			ans = ans + x
			k = k - 1
		i = i - 2
	if i != -1:
		for i in range(i, -1, -1):
			ans += arr[i]
	print(ans)


for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	lst = list(map(int, input().split()))
	lst.sort(reverse=True)
	s = 0
	i = 0
	while k > 0:
		if lst[i] + lst[i + 1] > x and k > 0:
			s += x
			i += 2
			k -= 1
		else:
			break
	for j in range(i, len(lst)):
		s += lst[j]
	print(s)


mod = 1000000007
from math import factorial, ceil, pow, sqrt, floor
from sys import stdin, stdout
from collections import defaultdict, Counter, deque
for _ in range(int(stdin.readline())):
	(n, k, x) = map(int, stdin.readline().split())
	li = list(map(int, stdin.readline().split()))
	li.sort()
	i = n
	ans = 0
	while i > 1:
		if k > 0:
			if x > li[i - 1] + li[i - 2]:
				ans += li[i - 1] + li[i - 2]
			else:
				ans += x
				k -= 1
			i -= 2
		else:
			ans += li[i - 1]
			i -= 1
	if i == 1:
		ans += li[0]
	print(ans)


for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	cost = 0
	while k > 0 and len(arr) > 1:
		sumc = arr[-1] + arr[-2]
		if sumc >= x:
			arr.pop(-1)
			arr.pop(-1)
			cost += x
			k -= 1
		else:
			break
	cost += sum(arr)
	print(cost)


import sys
for _ in range(int(sys.stdin.readline())):
	(n, k, x) = map(int, sys.stdin.readline().split())
	l = list(map(int, sys.stdin.readline().split()))
	new = sorted(l, reverse=True)
	ans = 0
	f = 0
	if n % 2:
		f = 1
		n -= 1
	for i in range(0, n, 2):
		if k == 0:
			for i in range(i, n):
				ans += new[i]
			break
		if new[i] + new[i + 1] <= x:
			ans += new[i] + new[i + 1]
		else:
			ans += x
			k -= 1
	if f == 1:
		ans += new[-1]
	print(ans)


import sys
from math import sqrt, ceil, floor, gcd
from collections import Counter
input = lambda : sys.stdin.readline()

def int_arr():
	return list(map(int, input().split()))

def str_arr():
	return list(map(str, input().split()))

def get_str():
	return map(str, input().split())

def get_int():
	return map(int, input().split())

def get_flo():
	return map(float, input().split())

def lcm(a, b):
	return a * b // gcd(a, b)
mod = 1000000007

def solve(n, k, x, arr):
	arr.sort(reverse=True)
	kpoint = 2 * k
	no = -1
	c = 0
	for i in range(0, 2 * k, 2):
		if arr[i] + arr[i + 1] < x:
			no = i
			break
		else:
			c += x
	if no != -1:
		for i in range(no, n):
			c += arr[i]
		print(c)
	else:
		for i in range(2 * k, n):
			c += arr[i]
		print(c)
for _ in range(int(input())):
	(n, k, x) = get_int()
	arr = int_arr()
	solve(n, k, x, arr)


import math, os, io, sys
from sys import stdin, stdout
from collections import Counter, deque, defaultdict
from itertools import product

def getList(method=int):
	return list(map(method, input().split()))

def getInt():
	return int(input())

def solve():
	(n, k, x) = getList()
	a = sorted(getList(), reverse=True)
	(i, k_) = (0, 0)
	while i + 1 < n:
		if a[i] + a[i + 1] < x or k_ == k:
			break
		k_ += 1
		i += 2
	return k_ * x + sum(a[i:])
for _ in range(getInt()):
	print(solve())


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	(n, k, x) = mp()
	l = sorted(li(), reverse=True)
	ans = 0
	for i in range(k):
		ans += min(l[2 * i] + l[2 * i + 1], x)
	for i in range(2 * k, n):
		ans += l[i]
	pr(ans)
for _ in range(inp()):
	solve()


for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	change = 0
	remove = 0
	for i in range(0, n, 2):
		if k > 0:
			if arr[i] + arr[i + 1] > x:
				change += x
				remove += arr[i] + arr[i + 1]
				k -= 1
			else:
				break
		else:
			break
	print(sum(arr) - remove + change)