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

```

Measured memory_bytes: 14211