1340C - Nastya and Unexpected Guest - CodeForces Solution

from collections import deque
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    return u * g + v

n, m = map(int, input().split())
d = list(map(int, input().split()))
d.sort()
g, r = map(int, input().split())
inf = pow(10, 9) + 1
l0, r0 = [inf] * m, [inf] * m
for i in range(m - 1):
    d0 = d[i + 1] - d[i]
    l0[i + 1], r0[i] = d0, d0
dp = [inf] * (m * g)
dp[0] = 0
q = deque([0])
c = 0
while q:
    v = q.popleft()
    i, j = divmod(v, g)
    for ni, nj in [(i - 1, j + l0[i]), (i + 1, j + r0[i])]:
        u = f(ni, nj % g)
        if nj < g and dp[u] == inf:
            dp[u] = dp[v]
            q.appendleft(u)
        elif nj == g and dp[u] == inf:
            dp[u] = dp[v] + 1
            q.append(u)
ans = inf
for i in range(m - 1, -1, -1):
    if d[i] + g < n:
        break
    ans = min(ans, dp[f(i, 0)] * (g + r) + n - d[i])
ans = (ans + 1) % (inf + 1) - 1
print(ans)