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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'try:\n# https://www.codechef.com/LTIME63B/problems/GHMC\n# Finally.... I properly understood what needs to be done.\n\n    def ctlt(arr, val):\n        # find number of values in sorted arr < val\n        if arr[0] >= val: return 0\n        lo = 0\n        hi = len(arr)\n        while hi-lo > 1:\n            md = (hi+lo)//2\n            if arr[md]<val:\n                lo = md\n            else:\n                hi = md\n\n        return hi\n\n    for _ in range(int(input())):\n        n,k,x,d = map(int, input().split())\n        z = input().strip().split()\n        if k > 0:\n            ps = list(map(int,z[:k]))\n        else:\n            ps = [x]\n\n        ps.sort()\n\n        if x<n or x<ps[-1] or n<k:\n            print(-1)\n            continue\n\n        valchecked = 0\n        fillval = 0\n        valsdone = False\n        isolbelow = True\n        lastp = ps[0]\n\n        while not valsdone and n>=k:\n            if n == k:\n                lo = x+d+1 # put out of range\n            else:\n            # find best maxfill (before val support)\n                lo = 1\n                hi = x+1\n                while hi-lo>1:\n                    md = (hi+lo)//2\n                    v = (x-md+1) + ctlt(ps,md)\n                    if v<n:\n                        hi = md\n                    else:\n                        lo = md\n        \n            valsdone = True\n            checkto = ctlt(ps,lo)-1\n            if checkto >= valchecked:            \n            # support all vals\n                for p in ps[valchecked+1:checkto+1]:\n                    if lastp+d >= p:\n                        isolbelow = False\n                    elif isolbelow:\n                        valsdone = False\n                        fillval += lastp+d\n                        n -= 1\n                        isolbelow = (p > lastp + 2*d )\n                    else:\n                        isolbelow = True\n                    lastp = p\n                valchecked = checkto\n                if valsdone and isolbelow: \n                # check gap to maxfill\n                    if lastp + d >= lo:\n                        isolbelow = False\n                    else:\n                        valsdone = False\n                        fillval += lastp\n                        ps[checkto] += d\n                        lastp += d\n                        isolbelow = False\n                        n -= 1\n\n        if k > n:\n            print(-1)\n        elif k == n:\n            print(sum(ps) + fillval)\n        elif k == n-1 and lo > ps[-1]:\n            print(sum(ps) + fillval + min(x,ps[-1]+d))\n        else:\n            tot = (x+lo)*(x-lo+1)//2  + sum(ps[:ctlt(ps,lo)])\n            print(tot + fillval)\nexcept:\n    pass'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14229