CF1340C Nastya and Unexpected Guest

如果女孩不去找 Denis，那么 Denis 就会去找女孩。根据这个规则，这位年轻人离开了家，买了花，前往 Nastya 的家。 从 Denis 家到女孩家的路上有一条宽度为 $n$ 的马路。这条马路并不总能在一个绿灯周期内全部通过。考虑到这一点，善良的市长决定在马路的某些位置设置安全岛。每个安全岛都位于一条线之后，并且在马路的起点和终点也有安全岛。行人可以在安全岛上休息、恢复体力并等待绿灯。 Denis 恰好在绿灯亮起的那一刻到达马路边。男孩知道，交通信号灯首先会亮 $g$ 秒绿灯，然后亮 $r$ 秒红灯，然后再次亮 $g$ 秒绿灯，如此循环。 形式化地，马路可以表示为区间 $[0, n]$。最初，Denis 位于 $0$ 点。他的任务是在最短时间内到达 $n$ 点。 他知道许多不同的整数 $d_1, d_2, \ldots, d_m$，其中 $0 \leq d_i \leq n$，这些点是安全岛的位置。在红灯亮起时，男孩只能停留在这些点中的某一个。 不幸的是，由于激动，Denis 并不总能控制自己，因此有如下限制： - 只要绿灯亮着，他必须一直移动，因为有如此美丽的女孩在等他，他很难停下来。Denis 每秒可以将自己的位置改变 $+1$ 或 $-1$，但必须始终保持在区间 $[0, n]$ 内。 - 他只能在安全岛上改变移动方向（因为那里安全）。也就是说，如果上一秒他的位置变化为 $+1$，并且他走到了安全岛上，那么他可以选择 $+1$ 或 $-1$ 继续移动。否则，他只能继续 $+1$。同理，如果上一秒他的位置变化为 $-1$，在安全岛上他可以选择 $+1$ 或 $-1$，在其他地方只能继续 $-1$。 - 在红灯亮起时，男孩必须位于某个安全岛上。绿灯亮起时，他可以朝任意方向继续移动。 当 Denis 的坐标等于 $n$ 时，他就算成功过马路。 这个任务并不简单，因为有可能根本无法过马路。由于 Denis 满脑子都是爱情，他无法解决这个问题，于是请求我们帮忙。请你帮他计算，在遵守所有规则的前提下，他最短需要多少时间才能过马路。如果无法过马路，输出 $-1$。

第一行包含两个整数 $n$ 和 $m$，$1 \leq n \leq 10^6, 2 \leq m \leq \min(n + 1, 10^4)$，分别表示马路宽度和安全岛数量。 第二行包含 $m$ 个互不相同的整数 $d_1, d_2, \ldots, d_m$，$0 \leq d_i \leq n$，表示安全岛的位置。保证 $0$ 和 $n$ 一定在其中。 第三行包含两个整数 $g, r$，$1 \leq g, r \leq 1000$，分别表示绿灯和红灯持续的时间。

输出一个整数，表示 Denis 遵守所有规则情况下过马路所需的最短时间。 如果无法过马路，输出 $-1$。

在第一个样例中，最优路线如下： - 第一个绿灯周期内，走到 $7$ 再返回到 $3$。此时在 $7$ 点（有安全岛）改变了方向，最后停在 $3$ 点（也有安全岛）。接下来需要等待 $11$ 秒红灯。 - 第二个绿灯周期内，走到 $14$。再次等待红灯。 - 用 $1$ 秒走到 $15$。此时 Denis 到达终点。 总共用时 $45$ 秒。 在第二个样例中，无法遵守所有规则过马路。 由 ChatGPT 4.1 翻译