← 返回题目列表

Codeforces · 2045/D

D. 水生龙

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

你生活在一个由 $$$N$$$ 岛屿(编号从 $$$1$$$ 到 $$$N$$$)组成的群岛中,这些岛屿排成一行。岛屿 $$$i$$$ 与岛屿 $$$i+1$$$ 相邻,对于 $$$1 \leq i < N$$$。在相邻岛屿 $$$i$$$ 和 $$$i+1$$$ 之间,有一对单向水下隧道:一条可让您从 $$$i$$$ 岛步行至 $$$i+1$$$ 岛,另一条则可反向。每条隧道最多只能穿过一次。

你身边还有一条龙。它具有由非负整数表示的耐力。龙需要耐力才能发挥其能力:游泳和飞行。最初,它的耐力为$$$0$$$。

你的龙的耐力可以按如下方式增加。每个岛屿$$$i$$$上都有一个神奇的神殿,当你第一次访问岛屿$$$i$$$时,它会立即增加你的龙的耐力$$$P_i$$$(无论龙的位置)。这个事件不需要时间。

当你在一个岛上时,你可以执行 $$$3$$$ 动作。

- 如果你的龙和你在同一个岛上,就和你的龙一起游到邻近的岛屿。如果你的龙的耐力至少为$$$D$$$,你就可以表演。这个动作会降低你龙的耐力$$$D$$$,并且需要$$$T_s$$$秒来执行。
- 如果你的龙和你在同一个岛上,就和你的龙一起飞到邻近的岛屿。如果你的龙的耐力不是$$$0$$$,你可以执行此动作。这个动作将你的龙的耐力设置为$$$0$$$,并且需要$$$T_f$$$秒来执行。
- 没有你的龙,独自通过水下隧道走到邻近的岛屿。此移动需要 $$$T_w$$$ 秒来执行。一旦你走过这条隧道,就不能再使用它。

请注意,游泳和飞行都不使用隧道。

你和你的龙目前在岛上$$$1$$$。你的任务是和你的龙一起去$$$N$$$岛。确定完成任务的最短可能时间。

输入

第一行由五个整数组成 $$$N$$$ $$$D$$$ $$$T_s$$$ $$$T_f$$$ $$$T_w$$$ ($$$2 \leq N \leq 200\,000; 1 \leq D, T_s, T_f, T_w \leq 200\,000$$$)。

第二行由 $$$N$$$ 整数 $$$P_i$$$ ($$$1 \leq P_i \leq 200\,000)$$$ 组成。

输出

在一行中输出一个整数,表示与你的龙一起去 $$$N$$$ 岛的最短可能时间。

示例

输入 #1

5 4 2 9 1
1 2 4 2 1

输出 #1

28

输入 #2

5 4 2 1 1
1 2 4 2 1

输出 #2

4

输入 #3

3 4 2 10 1
3 1 2

输出 #3

16

注意

示例输入/输出 #1 的说明

以下事件序列将在最短的时间内完成您的任务。

1. 岛上的神社$$$1$$$将你的龙的耐力增加到$$$1$$$。
2. 与你的龙一起飞到岛屿$$$2$$$。岛上的神社 $$$2$$$ 将你的龙的耐力增加到 $$$2$$$。
3. 独自步行去岛$$$3$$$。岛上的神社 $$$3$$$ 将你的龙的耐力增加到 $$$6$$$。
4. 独自步行去岛$$$4$$$。岛上的神社 $$$4$$$ 将你的龙的耐力增加到 $$$8$$$。
5. 独自步行去岛$$$3$$$。
6. 独自步行去岛$$$2$$$。
7. 与你的龙一起游到岛$$$3$$$。你的龙的耐力现在为$$$4$$$。
8. 与你的龙一起游到岛$$$4$$$。你的龙的耐力现在为$$$0$$$。
9. 独自步行去岛$$$5$$$。岛上的神社 $$$5$$$ 将你的龙的耐力增加到 $$$1$$$。
10.独自步行去岛$$$4$$$。
11. 与你的龙一起飞到岛屿$$$5$$$。

示例输入/输出#2 的说明

对于$$$1 \leq i < 5$$$重复以下过程:$$$i$$$岛上的神社会增加你的龙的耐力,然后使用耐力带着你的龙飞到岛$$$i+1$$$。