After six days, professor GukiZ decided to give more candies to his students. Like last time, he has $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 and positive.
- GukiZ didn't give more than $x$ candies to any student (the maximum value in the sequence $p$ is not greater than $x$).
- For each student $i$, there is at least one other student $j$ such that $|p_i - p_j| \le D$.
- 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.
GukiZ would like to know the total number of candies $S$ he had at the beginning. However, times change and after six days, the professor is really tired, so it is possible that there is no sequence $p$ which satisfies the constraints. Can you help GukiZ find the number of candies he gave out, or tell him that he must have made a mistake?

-----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 four space-separated integers $N$, $K$, $x$, $D$.
- The second line contains $K$ distinct 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, or $-1$ if there is no valid sequence $p$.

-----Constraints-----
- $1 \le T \le 50$
- $3 \le N \le 10^9$
- $1 \le K \le \mathrm{min}(N, 2 \cdot 10^4)$ 
- $1 \le x \le 2 \cdot 10^9$
- $1 \le D \le 10^9$
- $1 \le p_i \le x$ for each valid $i$
- All values $p_i$ from input are distinct

-----Subtasks-----
Subtask #1 (15 points): $1 \leq x, N, D \leq 15$ 
Subtask #2 (35 points): $1 \leq x, N, D \leq 10^5$ 
Subtask #3 (50 points): original constraints

-----Example Input-----
2
4 3 5 3
2 1 5
3 2 8 2
3 8

-----Example Output-----
12
-1

-----Explanation-----
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 maximum possible amount of candies given to some student is $x=5$. The best possible option is giving $p_4=4$ candies to the last student. Then, the fourth constraint (with $D=3$) is satisfied for all students. Only the pair of students $(2, 3)$ have numbers of candies that differ by more than $3$, but still, for each student, there are at least two other students with close enough numbers of candies.
Example case 2: GukiZ made some mistake in distribution and there is no valid sequence $p$. The answer is $-1$.

Source: codechef | Difficulty: VERY_HARD
Tags: Sorting

Constructive algorithms


Solutions:
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
for _ in range(int(input())):
	(n, k, x, d) = map(int, input().split())
	z = input().strip().split()
	if k > 0:
		ps = list(map(int, z[:k]))
	else:
		ps = [x]
	ps.sort()
	if x < n or x < ps[-1] or n < k:
		print(-1)
		continue
	valchecked = 0
	fillval = 0
	valsdone = False
	isolbelow = True
	lastp = ps[0]
	while not valsdone and n >= k:
		if n == k:
			lo = x + d + 1
		else:
			lo = 1
			hi = x + 1
			while hi - lo > 1:
				md = (hi + lo) // 2
				v = x - md + 1 + ctlt(ps, md)
				if v < n:
					hi = md
				else:
					lo = md
		valsdone = True
		checkto = ctlt(ps, lo) - 1
		if checkto >= valchecked:
			for p in ps[valchecked + 1:checkto + 1]:
				if lastp + d >= p:
					isolbelow = False
				elif isolbelow:
					valsdone = False
					fillval += lastp + d
					n -= 1
					isolbelow = p > lastp + 2 * d
				else:
					isolbelow = True
				lastp = p
			valchecked = checkto
			if valsdone and isolbelow:
				if lastp + d >= lo:
					isolbelow = False
				else:
					valsdone = False
					fillval += lastp
					ps[checkto] += d
					lastp += d
					isolbelow = False
					n -= 1
	if k > n:
		print(-1)
	elif k == n:
		print(sum(ps) + fillval)
	elif k == n - 1 and lo > ps[-1]:
		print(sum(ps) + fillval + min(x, ps[-1] + d))
	else:
		tot = (x + lo) * (x - lo + 1) // 2 + sum(ps[:ctlt(ps, lo)])
		print(tot + fillval)


def solve(p, n, x, d):
	if x < n:
		return -1
	k = len(p)
	n -= k
	ret = sum(p)
	p = sorted(p)
	cur = 0
	sss = set()
	sss.update(p)
	while cur < k:
		if cur < k - 1 and p[cur + 1] - p[cur] <= d:
			cur += 1
			continue
		if cur > 0 and p[cur] - p[cur - 1] <= d:
			cur += 1
			continue
		val = min(p[cur] + d, x)
		while val in sss:
			val -= 1
		sss.add(val)
		while cur < k and p[cur] <= val + d:
			cur += 1
		n -= 1
		ret += val
	if n < 0:
		return -1
	if n == 0:
		return ret
	if n == 1:
		v = max(sss)
		z = min(v + d, x)
		while z in sss:
			z -= 1
		return ret + z
	q = sorted(sss)[::-1]
	for z in q:
		if x - z >= n:
			w = x * (x + 1) // 2 - (x - n) * (x - n + 1) // 2
			return ret + w
		ret -= z
		n += 1
	w = x * (x + 1) // 2 - (x - n) * (x - n + 1) // 2
	return ret + w
import sys
f = sys.stdin
t = int(f.readline())
for i in range(t):
	(n, k, x, d) = map(int, f.readline().split())
	p = list(map(int, f.readline().split()))
	q = solve(p, n, x, d)
	print(q)