------Read problems statements in Mandarin chinese
, Russian and Vietnamese as well. ------ 

Professor GukiZ decided to distribute all of his candies to his $N$ students (numbered $1$ through $N$). Let's denote the number of candies GukiZ gave to the $i$-th student by $p_{i}$. As GukiZ has a lot of students, he does not remember all the exact numbers of candies he gave to the students. He only remembers the following properties of the sequence $p$:
The numbers of candies given to each of the first $K$ students ($p_{1}, p_{2}, \dots, p_{K}$) are known exactly.
All elements of the sequence $p$ are distinct.
The difference between the maximum and minimum element of the sequence $p$ does not exceed $x$.
The professor gave out the biggest possible total number of candies, i.e. $S = p_{1} + p_{2} + p_{3} + \ldots + p_{N}$ is maximum possible.

Normally, professors never lie, so the information provided by GukiZ is valid and there is at least one sequence that satisfies all conditions. GukiZ would like to know the total number of candies $S$ he had at the beginning. Can you help him find this number?

------  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 three space-separated integers $N$, $K$ and $x$.
The second line contains $K$ space-separated integers $p_{1}, p_{2}, \dots, p_{K}$.

------  Output ------
For each test case, print a single line containing one integer — the number of candies GukiZ had.

------  Constraints ------
$1 ≤ T ≤ 50$
$1 ≤ N ≤ 10^{9}$
$1 ≤ K ≤ \mathrm{min}(N, 2 \cdot 10^{4})$ 
$0  ≤ x ≤ 10^{9}$
$1 ≤ p_{i} ≤ 10^{9}$ for each valid $i$
there is at least one valid distribution of candies to students

----- Sample Input 1 ------ 
2
4 3 4 
2 1 5
2 2 9
3 6
----- Sample Output 1 ------ 
12
9
----- explanation 1 ------ 
Example case 1: There are four students. We know that the first student got $p_{1} = 2$ candies, the second student got $p_{2} = 1$ and the third got $p_{3} = 5$ candies; we don't know the number of candies given to the last student. The difference between the maximum and minimum number of candies given to students is already $5-1 = 4 = x$, so the fourth student could only have been given between $1$ and $5$ candies. It can't be $5$ either, so we maximize the number of candies if we give $4$ candies to the fourth student. In total, there are $2 + 1 + 5 + 4 = 12$ candies.

Example case 2: We know the number of candies given to each of the two students, so we know that GukiZ had $3 + 6 = 9$ candies.

Difficulty: HARD
Tags: Sorting
Skill types: Sorting

Starter code:

Solutions:
for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	candies = sorted(map(int, input().split()), reverse=True)
	M = candies[-1] + x
	ans = sum(candies)
	i = 0
	req = n - k
	while req:
		if M > candies[i]:
			c = candies[i]
			if M - req >= c:
				y = M - req
				ans += M * (M + 1) // 2 - y * (y + 1) // 2
				break
			else:
				ans += M * (M + 1) // 2 - c * (c + 1) // 2
				req -= M - c
				M = c - 1
				i += 1
		else:
			M = candies[i] - 1
			i += 1
	print(ans)


from sys import stdin, stdout
from collections import defaultdict
for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	l = list(map(int, input().split()))
	mini = min(l)
	high = mini + x
	d = defaultdict(int)
	for i in l:
		d[i] += 1
	c = n - k
	e = high
	s = high - c + 1
	ans = c * (2 * s + c - 1) // 2
	cur = s - 1
	for i in l:
		if s <= i <= e:
			while d[cur]:
				cur -= 1
			ans += cur
			cur -= 1
		else:
			ans += i
	print(ans)


from collections import Counter

def tot(n):
	return n * (n + 1) // 2
for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	arr.sort()
	sm = sum(arr)
	c = Counter(arr)
	ma = arr[0] + x
	hi = ma
	lo = 0
	dist = n - k
	if dist == 0:
		print(sum(arr))
		continue
	from bisect import bisect_right as br

	def check(mi):
		return ma - mi + 1 - (k - br(arr, mi - 1)) >= dist
	while lo <= hi:
		mi = lo + hi >> 1
		if check(mi):
			ans = mi
			lo = mi + 1
		else:
			hi = mi - 1
	sm = tot(ma) - tot(ans - 1) - sum([i for i in arr if i >= ans]) + sum(arr)
	print(sm)


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


def ctlt(arr, val):
	if arr[0] >= val:
		return 0
	lo = 0
	hi = len(arr)
	while hi - lo > 1:
		md = (hi + lo) // 2
		if arr[md] < val:
			lo = md
		else:
			hi = md
	return hi

def solve(n, k, x, ps):
	if k == n:
		return sum(ps)
	ps.sort()
	mxc = ps[0] + x
	lo = 1
	hi = mxc + 1
	while hi - lo > 1:
		md = (hi + lo) // 2
		v = mxc - md + 1 + ctlt(ps, md)
		if v < n:
			hi = md
		else:
			lo = md
	tot = (mxc + lo) * (mxc - lo + 1) // 2 + sum(ps[:ctlt(ps, lo)])
	return tot
for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	z = input().strip().split()
	ps = list(map(int, z[:k]))
	print(solve(n, k, x, ps))


import sys
t = int(sys.stdin.readline().strip())
for _ in range(t):
	(n, k, x) = map(int, sys.stdin.readline().strip().split())
	l = list(map(int, sys.stdin.readline().strip().split()))
	maxx = max(l)
	minn = min(l)
	total = sum(l)
	if n == k:
		print(total)
		continue
	remaining = n - k
	if maxx - minn < x:
		maxx = minn + x
		total += maxx
		remaining -= 1
		l.append(maxx)
	l.sort()
	i = len(l) - 1
	while remaining:
		if l[i] - l[i - 1] > 1:
			diff = min(remaining, l[i] - l[i - 1] - 1)
			remaining -= diff
			x = l[i] - diff - 1
			x = (x * x + x) // 2
			y = (l[i] * l[i] - l[i]) // 2
			total += y - x
		i -= 1
	print(total)


for _ in range(int(input())):
	(n, k, x) = map(int, input().split())
	a = list(map(int, input().split()))
	s = sum(a)
	if n == k:
		print(s)
	else:
		a.sort()
		m = min(a)
		d = m + x
		b = d - n + k + 1
		s += int(d * (d + 1) // 2 - b * (b - 1) // 2)
		for i in range(k - 1, -1, -1):
			if a[i] >= b:
				s -= a[i]
				s += b - 1
				b -= 1
			else:
				break
		print(s)


import math as ma
from sys import exit
from decimal import Decimal as dec
from itertools import permutations

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

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x

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

def nu():
	return int(input())

def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
t = nu()
for it in range(t):
	(n, k, x) = num()
	a = li()
	if k == n:
		print(sum(a))
		continue
	a.sort()
	mp = min(a)
	mx = max(a)
	if mx - mp == x:
		a = a[::-1]
		cc = k
		i = 0
		s = sum(a)
		while i < k - 1 and cc < n:
			zz = a[i] - a[i + 1] - 1
			ll = n - cc
			if ll >= zz:
				s += a[i] * zz - zz * (zz + 1) // 2
				cc += zz
			else:
				s += a[i] * ll - ll * (ll + 1) // 2
				cc += ll
			i += 1
		print(s)
	else:
		i = 0
		pp = mp + x
		a.append(pp)
		a.sort()
		a = a[::-1]
		cc = k + 1
		s = sum(a)
		while i < k and cc < n:
			zz = a[i] - a[i + 1] - 1
			ll = n - cc
			if ll >= zz:
				s += a[i] * zz - zz * (zz + 1) // 2
				cc += zz
			else:
				s += a[i] * ll - ll * (ll + 1) // 2
				cc += ll
			i += 1
		print(s)


for i in range(int(input())):
	(n, k, x) = (int(s) for s in input().split())
	l = sorted([int(s) for s in input().split()])
	ans = sum(l)
	m = l[0]
	w = x + m
	j = -1
	count = k
	while count < n:
		r = l[j]
		j -= 1
		if w - r <= n - count:
			ans += w * (w + 1) // 2 - r * (r + 1) // 2
			count += w - r
			w = r - 1
		else:
			r1 = n - count
			ans += w * (w + 1) // 2 - (w - r1) * (w - r1 + 1) // 2
			count += r1
	print(ans)


def total(p, q):
	return (q - p + 1) * (p + q) >> 1
t = int(input())
for _ in range(t):
	(n, k, x) = map(int, input().split())
	a = sorted(list(map(int, input().split())), reverse=True)
	s = sum(a)
	v = a[-1] + x
	c = n - k
	for i in range(k):
		if v - a[i] < c:
			s += total(a[i] + 1, v)
			c -= v - a[i]
			v = a[i] - 1
		else:
			s += total(v - c + 1, v)
			c = 0
			break
	print(s)


I = lambda : map(int, input().split())
t = int(input())
for i in range(t):
	(n, k, x) = I()
	a = list(I())
	a.sort()
	smm = sum(a)
	minn = a[0]
	l = minn + x
	j = n - k
	t = 1
	while j > 0 and t <= k:
		h = max(a[-t], l - j)
		smm += l * (l + 1) // 2 - h * (h + 1) // 2
		j -= l - h
		l = h - 1
		t += 1
	if j > 0:
		smm += (a[0] - 1) * a[0] // 2 - (a[0] - 1 - j) * (a[0] - j) // 2
	print(smm)


t = int(input())
for i in range(t):
	(n, k, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	su = sum(a)
	mi = a[0]
	l = mi + x
	j = n - k
	t = 1
	while j > 0 and t <= k:
		h = max(a[-t], l - j)
		su += l * (l + 1) // 2 - h * (h + 1) // 2
		j -= l - h
		l = h - 1
		t += 1
	if j > 0:
		su += (a[0] - 1) * a[0] // 2 - (a[0] - 1 - j) * (a[0] - j) // 2
	print(su)


for _ in range(int(input())):
	(N, K, X) = map(int, input().split())
	P = list(map(int, input().split()))
	P.sort(reverse=True)
	maxP = P[-1] + X
	if N == K:
		print(sum(P))
	elif X + 1 == N:
		print((P[-1] + maxP) * (X + 1) // 2)
	else:
		j = 0
		while maxP - P[j] + K - j < N:
			j = j + 1
		nt = N - K + j
		print(sum(P[j:]) + nt * (2 * maxP - nt + 1) // 2)


def bruteForceMethod():
	candiesGiven = sum(P)
	smallestCandy = min(P)
	biggestCandy = min(P) + X
	extraStudents = N - K
	candiesToGive = biggestCandy
	while extraStudents > 0:
		if candiesToGive in P:
			candiesToGive -= 1
			continue
		else:
			candiesGiven += candiesToGive
			extraStudents -= 1
			candiesToGive -= 1
			continue
	return candiesGiven

def quickSum(A, B):
	triangular = lambda n: n * (n + 1) // 2
	(A, B) = (min(A, B), max(A, B))
	return triangular(B) - triangular(A - 1)

def fastMethod():
	candiesGiven = sum(P)
	smallestCandy = min(P)
	extraStudents = N - K
	if extraStudents == 0:
		return candiesGiven
	candiesToGiveStart = min(P) + X
	candiesToGiveEnd = candiesToGiveStart - extraStudents + 1
	clashingStudentsAmounts = [x for x in P if candiesToGiveStart >= x >= candiesToGiveEnd]
	candiesGiven -= sum(clashingStudentsAmounts)
	clashingStudents = len(clashingStudentsAmounts)
	candiesGiven += quickSum(candiesToGiveStart, candiesToGiveEnd)
	while clashingStudents > 0:
		candiesToGiveStart -= extraStudents
		candiesToGiveEnd = candiesToGiveStart - clashingStudents + 1
		extraStudents = clashingStudents
		clashingStudentsAmounts = [x for x in P if candiesToGiveStart >= x >= candiesToGiveEnd]
		candiesGiven -= sum(clashingStudentsAmounts)
		clashingStudents = len(clashingStudentsAmounts)
		candiesGiven += quickSum(candiesToGiveStart, candiesToGiveEnd)
	return candiesGiven
T = int(input())
for _ in range(T):
	(N, K, X) = [int(x) for x in input().split()]
	P = [int(x) for x in input().split()]
	print(fastMethod())


for _ in range(int(input())):
	(n, k, x) = [int(i) for i in input().split()]
	p = [int(i) for i in input().split()]
	p.sort()
	x = min(p) + x
	s = x * (x + 1) // 2 - (x - n) * (x - n + 1) // 2
	c = x - n + 1
	for i in range(k):
		if p[i] < c:
			s = s - c + p[i]
			c += 1
	print(s)


t = int(input())
for _ in range(t):
	(n, k, x) = map(int, input().split())
	s = list(map(int, input().split()))
	ul = min(s) + x
	ll = ul - n
	ssm = ul * (ul + 1) // 2 - ll * (ll + 1) // 2
	s.sort()
	ll += 1
	for i in s:
		if i < ll:
			ssm -= ll - i
			ll += 1
	print(ssm)


def main():
	t = int(input())
	for _ in range(t):
		(n, k, x) = [int(x) for x in input().split()]
		a = [int(x) for x in input().split()]
		a.sort()
		mina = min(a)
		maxpa = mina + x
		tofill = n - k
		elem = maxpa
		ans = sum(a)
		idx = -1
		ce = a[idx]
		while k < n:
			if maxpa == ce:
				maxpa -= 1
			if maxpa > ce:
				fil = maxpa - ce
				if fil < n - k:
					ans += (maxpa * (maxpa + 1) - ce * (ce + 1)) // 2
					k += fil
				else:
					ans += (maxpa * (maxpa + 1) - (maxpa - (n - k)) * (maxpa - (n - k) + 1)) // 2
					k = n
					break
				maxpa = ce - 1
			idx -= 1
			ce = a[idx]
		print(ans)
main()