If the girl doesn't go to Denis, then Denis will go to the girl. Using this rule, the young man left home, bought flowers and went to Nastya. 

On the way from Denis's house to the girl's house is a road of $n$ lines. This road can't be always crossed in one green light. Foreseeing this, the good mayor decided to place safety islands in some parts of the road. Each safety island is located after a line, as well as at the beginning and at the end of the road. Pedestrians can relax on them, gain strength and wait for a green light.

Denis came to the edge of the road exactly at the moment when the green light turned on. The boy knows that the traffic light first lights up $g$ seconds green, and then $r$ seconds red, then again $g$ seconds green and so on.

Formally, the road can be represented as a segment $[0, n]$. Initially, Denis is at point $0$. His task is to get to point $n$ in the shortest possible time.

He knows many different integers $d_1, d_2, \ldots, d_m$, where $0 \leq d_i \leq n$  — are the coordinates of points, in which the safety islands are located. Only at one of these points, the boy can be at a time when the red light is on.

Unfortunately, Denis isn't always able to control himself because of the excitement, so some restrictions are imposed:  He must always move while the green light is on because it's difficult to stand when so beautiful girl is waiting for you. Denis can change his position by $\pm 1$ in $1$ second. While doing so, he must always stay inside the segment $[0, n]$.  He can change his direction only on the safety islands (because it is safe). This means that if in the previous second the boy changed his position by $+1$ and he walked on a safety island, then he can change his position by $\pm 1$. Otherwise, he can change his position only by $+1$. Similarly, if in the previous second he changed his position by $-1$, on a safety island he can change position by $\pm 1$, and at any other point by $-1$.  At the moment when the red light is on, the boy must be on one of the safety islands. He can continue moving in any direction when the green light is on. 

Denis has crossed the road as soon as his coordinate becomes equal to $n$.

This task was not so simple, because it's possible that it is impossible to cross the road. Since Denis has all thoughts about his love, he couldn't solve this problem and asked us to help him. Find the minimal possible time for which he can cross the road according to these rules, or find that it is impossible to do.


-----Input-----

The first line contains two integers $n$ and $m$ $(1 \leq n \leq 10^6, 2 \leq m \leq min(n + 1, 10^4))$  — road width and the number of safety islands.

The second line contains $m$ distinct integers $d_1, d_2, \ldots, d_m$ $(0 \leq d_i \leq n)$  — the points where the safety islands are located. It is guaranteed that there are $0$ and $n$ among them.

The third line contains two integers $g, r$ $(1 \leq g, r \leq 1000)$  — the time that the green light stays on and the time that the red light stays on.


-----Output-----

Output a single integer  — the minimum time for which Denis can cross the road with obeying all the rules.

If it is impossible to cross the road output $-1$.


-----Examples-----
Input
15 5
0 3 7 14 15
11 11

Output
45
Input
13 4
0 3 7 13
9 9

Output
-1


-----Note-----

In the first test, the optimal route is:       for the first green light, go to $7$ and return to $3$. In this case, we will change the direction of movement at the point $7$, which is allowed, since there is a safety island at this point. In the end, we will be at the point of $3$, where there is also a safety island. The next $11$ seconds we have to wait for the red light.      for the second green light reaches $14$. Wait for the red light again.      for $1$ second go to $15$. As a result, Denis is at the end of the road. 

In total, $45$ seconds are obtained.

In the second test, it is impossible to cross the road according to all the rules.

Difficulty: MEDIUM

Starter code:

Solutions:
import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def output(*args):
	sys.stdout.buffer.write(('\n'.join(map(str, args)) + '\n').encode('utf-8'))

def main():
	from collections import deque
	(n, m) = map(int, input().split())
	pos = [-10 ** 9] + sorted(map(int, input().split())) + [10 ** 9]
	(g, r) = map(int, input().split())
	inf = 10 ** 9
	dp = [array('i', [inf]) * (g + 1) for _ in range(m + 2)]
	dp[1][0] = 0
	dq = deque([(1, 0)])
	while dq:
		(v, time) = dq.popleft()
		(p_dist, n_dist) = (pos[v] - pos[v - 1], pos[v + 1] - pos[v])
		if time == g:
			if p_dist <= g and dp[v - 1][p_dist] > dp[v][time] + 1:
				dp[v - 1][p_dist] = dp[v][time] + 1
				dq.append((v - 1, p_dist))
			if n_dist <= g and dp[v + 1][n_dist] > dp[v][time] + 1:
				dp[v + 1][n_dist] = dp[v][time] + 1
				dq.append((v + 1, n_dist))
		else:
			if time + p_dist <= g and dp[v - 1][time + p_dist] > dp[v][time]:
				dp[v - 1][time + p_dist] = dp[v][time]
				dq.appendleft((v - 1, time + p_dist))
			if time + n_dist <= g and dp[v + 1][time + n_dist] > dp[v][time]:
				dp[v + 1][time + n_dist] = dp[v][time]
				dq.appendleft((v + 1, time + n_dist))
	ans = min((dp[-2][i] * (g + r) + i for i in range(g + 1)))
	print(ans if ans < inf else -1)
main()


import collections
(n, m) = map(int, input().split())
m += 2
arr = list(map(int, input().split()))
arr.append(0)
arr.append(n)
arr = sorted(arr)
(g, r) = map(int, input().split())
q = collections.deque()
q.append((0, 0))
dist = [[0] * (g + 1) for _ in range(m + 2)]
checked = [[0] * (g + 1) for _ in range(m + 2)]
checked[0][0] = 1
ans = -1
while len(q) != 0:
	(v, t) = q.popleft()
	if t == 0:
		if n - arr[v] <= g:
			tmp = dist[v][t] * (g + r) + n - arr[v]
			if ans == -1 or ans > tmp:
				ans = tmp
	if t == g:
		if checked[v][0] == 0:
			checked[v][0] = 1
			dist[v][0] = dist[v][t] + 1
			q.append((v, 0))
		continue
	if v != 0:
		cost = t + arr[v] - arr[v - 1]
		if cost <= g and checked[v - 1][cost] == 0:
			checked[v - 1][cost] = 1
			dist[v - 1][cost] = dist[v][t]
			q.appendleft((v - 1, cost))
	if v != m - 1:
		cost = t + arr[v + 1] - arr[v]
		if cost <= g and checked[v + 1][cost] == 0:
			checked[v + 1][cost] = 1
			dist[v + 1][cost] = dist[v][t]
			q.appendleft((v + 1, cost))
print(ans)


import collections
(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
arr = sorted(arr)
(g, r) = map(int, input().split())
q = collections.deque()
q.append((0, 0, 0))
checked = [[-1] * g for _ in range(m)]
checked[0][0] = 0
while len(q) != 0:
	(v, t, cnt) = q.popleft()
	if v != m - 1:
		cost1 = arr[v + 1] - arr[v]
		if t + cost1 <= g:
			if checked[v + 1][(t + cost1) % g] == -1:
				if t + cost1 < g:
					q.appendleft((v + 1, t + cost1, cnt))
					checked[v + 1][t + cost1] = cnt
				else:
					q.append((v + 1, 0, cnt + 1))
					checked[v + 1][0] = cnt + 1
	if v != 0:
		cost2 = arr[v] - arr[v - 1]
		if t + cost2 <= g:
			if checked[v - 1][(t + cost2) % g] == -1:
				if t + cost2 < g:
					q.appendleft((v - 1, t + cost2, cnt))
					checked[v - 1][t + cost2] = cnt
				else:
					q.append((v - 1, 0, cnt + 1))
					checked[v - 1][0] = cnt + 1
ans = 10 ** 18
for i in range(m):
	for j in range(g):
		if checked[i][j] == -1:
			continue
		elif j + n - arr[i] <= g:
			ans = min(ans, checked[i][j] * (g + r) + j + n - arr[i])
if ans == 10 ** 18:
	print(-1)
else:
	print(ans)


import sys
input = sys.stdin.readline
from collections import deque
from typing import List

def inp():
	return int(input())

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

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

def compute(n, m, g, r, A: List[int]):
	A.sort()
	WHITE = -1
	GREY = -2
	states = [[WHITE] * (g + 1) for _ in range(m)]
	states[0][g] = 0
	states[0][0] = 0
	q = deque([(0, g)])

	def process_neib(ineib, gneib):
		if states[ineib][gneib] != WHITE:
			return
		if ineib == m - 1:
			states[ineib][gneib] = states[index][g_left]
		elif gneib == 0:
			states[ineib][gneib] = states[index][g_left] + 1
			states[ineib][g] = states[ineib][gneib]
			gneib = g
			q.append((ineib, gneib))
		else:
			states[ineib][gneib] = states[index][g_left]
			q.appendleft((ineib, gneib))
	while q:
		(index, g_left) = q.popleft()
		if index > 0:
			delta = A[index] - A[index - 1]
			if g_left >= delta:
				process_neib(index - 1, g_left - delta)
		if index < m - 1:
			delta = A[index + 1] - A[index]
			if g_left >= delta:
				process_neib(index + 1, g_left - delta)
	res = float('inf')
	for g_left in range(g):
		if states[m - 1][g_left] >= 0:
			res = min(res, states[m - 1][g_left] * (r + g) + g - g_left)
	if res != float('inf'):
		print(res)
	else:
		print('-1')

def from_file(f):
	return f.readline
(n, m) = invr()
A = inlt()
(g, r) = invr()
compute(n, m, g, r, A)


import sys
sys.setrecursionlimit(10000)
from collections import deque
from heapq import heappush, heappop

class Memoize:

	def __init__(self, f):
		self.f = f
		self.memo = {}

	def __call__(self, *args):
		if not args in self.memo:
			self.memo[args] = self.f(*args)
		return self.memo[args]

class Recurse(Exception):

	def __init__(self, *args, **kwargs):
		self.args = args
		self.kwargs = kwargs

def recurse(*args, **kwargs):
	raise Recurse(*args, **kwargs)

def tail_recursive(f):

	def decorated(*args, **kwargs):
		while True:
			try:
				return f(*args, **kwargs)
			except Recurse as r:
				args = r.args
				kwargs = r.kwargs
				continue
	return decorated
(n, m) = list(map(int, input().split()))
d = sorted(map(int, input().split()))
(g, r) = list(map(int, input().split()))
q = deque([(0, 0, g)])
cost = [[-1] * (g + 1) for _ in range(m)]
while len(q):
	(c, x, t) = q.popleft()
	if cost[x][t] != -1:
		continue
	cost[x][t] = c
	back = False
	if t == 0:
		back = True
		c += r
		t = g
	for di in [-1, 1]:
		ni = x + di
		if ni >= 0 and ni < m:
			step = abs(d[x] - d[ni])
			if step <= t:
				if back:
					q.append((c + step, ni, t - step))
				else:
					q.appendleft((c + step, ni, t - step))
res = list([x for x in cost[m - 1] if x != -1])
print(min(res) if len(res) else -1)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

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

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

def N():
	return int(input())
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
mod = 10 ** 9 + 7
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	fact(x, mod)
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa.reverse()

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def floorsum(a, b, c, n):
	if a == 0:
		return b // c * (n + 1)
	if a >= c or b >= c:
		return floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2
	m = (a * n + b) // c
	return n * m - floorsum(c, c - b - 1, a, m - 1)

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

def lowbit(n):
	return n & -n

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class ST:

	def __init__(self, arr):
		n = len(arr)
		mx = n.bit_length()
		self.st = [[0] * mx for i in range(n)]
		for i in range(n):
			self.st[i][0] = arr[i]
		for j in range(1, mx):
			for i in range(n - (1 << j) + 1):
				self.st[i][j] = max(self.st[i][j - 1], self.st[i + (1 << j - 1)][j - 1])

	def query(self, l, r):
		if l > r:
			return -inf
		s = (r + 1 - l).bit_length() - 1
		return max(self.st[l][s], self.st[r - (1 << s) + 1][s])

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] > self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		seen.add(u)
		for (v, w) in graph[u]:
			if v not in d or d[v] > d[u] + w:
				d[v] = d[u] + w
				heappush(heap, (d[v], v))
	return d

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]

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

def lis(nums):
	res = []
	for k in nums:
		i = bisect.bisect_left(res, k)
		if i == len(res):
			res.append(k)
		else:
			res[i] = k
	return len(res)

def RP(nums):
	n = len(nums)
	s = set(nums)
	d = {}
	for (i, k) in enumerate(sorted(s), 1):
		d[k] = i
	bi = BIT([0] * (len(s) + 1))
	ans = 0
	for i in range(n - 1, -1, -1):
		ans += bi.query(d[nums[i]] - 1)
		bi.update(d[nums[i]], 1)
	return ans

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

def topo(n):
	q = deque()
	res = []
	for i in range(1, n + 1):
		if ind[i] == 0:
			q.append(i)
			res.append(i)
	while q:
		u = q.popleft()
		for v in g[u]:
			ind[v] -= 1
			if ind[v] == 0:
				q.append(v)
				res.append(v)
	return res

@bootstrap
def gdfs(r, p):
	if len(g[r]) == 1 and p != -1:
		yield None
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None
from collections import deque
t = 1
for i in range(t):
	(n, m) = RL()
	d = RLL()
	inf = 10 ** 9
	d = [-inf] + sorted(d) + [inf]
	(g, r) = RL()
	q = deque([(1, 0)])
	vis = [0] * ((m + 1) * g)
	dis = [inf] * ((m + 1) * g)
	vis[0] = 1
	dis[0] = 0
	cur = 0
	ans = inf
	f = False
	while q:
		nq = deque()
		while q:
			(u, t) = q.popleft()
			if u == m:
				if t != 0:
					ans = min(ans, cur * (g + r) + t)
				else:
					ans = min(ans, cur * g + (cur - 1) * r)
				f = True
				continue
			if t + d[u] - d[u - 1] < g and (not vis[(u - 2) * g + t + d[u] - d[u - 1]]):
				vis[(u - 2) * g + t + d[u] - d[u - 1]] = 1
				q.append((u - 1, t + d[u] - d[u - 1]))
			elif t + d[u] - d[u - 1] == g and (not vis[(u - 2) * g]):
				vis[(u - 2) * g] = 1
				nq.append((u - 1, 0))
			if t - d[u] + d[u + 1] < g and (not vis[u * g + t - d[u] + d[u + 1]]):
				vis[u * g + t - d[u] + d[u + 1]] = 1
				q.append((u + 1, t - d[u] + d[u + 1]))
			elif t - d[u] + d[u + 1] == g and (not vis[u * g]):
				vis[u * g] = 1
				nq.append((u + 1, 0))
		if f:
			print(ans)
			exit()
		q = nq
		cur += 1
	print(-1)