← 返回题目列表

Codeforces · 1340/C

C. 纳斯蒂亚和意外的客人

中文机器翻译题面 查看原题

如果女孩不去找丹尼斯,那么丹尼斯就会去找女孩。利用这个规则,年轻人离开家,买了花,去了娜斯佳。

从丹尼斯家到女孩家的路上有一条$$$n$$$线的路。这条路不可能总是一绿灯就可以通过。预见到这一点,好心的市长决定在道路的某些部分设置安全岛。每个安全岛都位于一条线之后以及道路的起点和终点。行人可以在上面放松、恢复体力并等待绿灯。

就在绿灯亮起的那一刻,丹尼斯来到了路边。男孩知道交通灯首先亮起 $$$g$$$ 秒绿灯,然后 $$$r$$$ 秒亮红灯,然后再次亮起 $$$g$$$ 秒绿灯,依此类推。

形式上,道路可以表示为一段$$$[0, n]$$$。最初,丹尼斯位于 $$$0$$$ 点。他的任务是在尽可能短的时间内到达$$$n$$$ 点。

他知道许多不同的整数 $$$d_1, d_2, \ldots, d_m$$$,其中 $$$0 \leq d_i \leq n$$$ — 是安全岛所在点的坐标。只有在其中一个时刻,男孩才能处于红灯亮起的时刻。

不幸的是,丹尼斯总是因为兴奋而无法控制自己,所以施加了一些限制:

- 当绿灯亮起时,他必须始终移动,因为当如此美丽的女孩在等你时,很难站立。 Denis 可以在 $$$1$$$ 秒内通过 $$$\pm 1$$$ 改变他的位置。这样做时,他必须始终留在 $$$[0, n]$$$ 段内。
- 他只能在安全岛上改变方向(因为那里很安全)。这意味着,如果男孩在前一秒改变了位置$$$+1$$$并且走上了安全岛,那么他可以改变位置$$$\pm 1$$$。否则,他只能通过$$$+1$$$改变他的位置。类似地,如果在前一秒他将位置改变了$$$-1$$$,那么在安全岛上他可以将位置改变$$$\pm 1$$$,并且在任何其他点改变位置$$$-1$$$。
- 红灯亮起的那一刻,男孩一定在其中一个安全岛上。当绿灯亮起时,他可以继续向任何方向移动。

一旦丹尼斯的坐标等于$$$n$$$,他就过马路了。

这个任务没那么简单,因为有可能无法过马路。由于丹尼斯一心想着他的爱情,他无法解决这个问题,并请求我们帮助他。根据这些规则找出他可以过马路的最短可能时间,或者发现这是不可能的。

输入

第一行包含两个整数 $$$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)$$$ — 绿灯亮的时间和红灯亮的时间。

输出

输出一个整数——丹尼斯在遵守所有规则的情况下过马路的最短时间。

如果不可能过马路,输出$$$-1$$$。

示例

输入 #1

15 5
0 3 7 14 15
11 11

输出 #1

45

输入 #2

13 4
0 3 7 13
9 9

输出 #2

-1

注意

第一次测试中,最优路线为:

- 第一个绿灯,前往$$$7$$$并返回$$$3$$$。在这种情况下,我们将在 $$$7$$$ 点改变移动方向,这是允许的,因为该点有一个安全岛。最后,我们将到达$$$3$$$点,那里还有一个安全岛。接下来的 $$$11$$$ 秒我们必须等待红灯。
- 第二次绿灯达到$$$14$$$。再次等待红灯。
- 对于 $$$1$$$ 第二个转到 $$$15$$$。结果,丹尼斯走到了路的尽头。

总共获得$$$45$$$秒。

在第二次测试中,按照所有规则是不可能过马路的。