P15671 [ICPC 2024 Jakarta R] Aquatic Dragon

你生活在一个由 $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 的解释** 以下事件序列将以最短时间完成你的任务： 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$。 翻译由 DeepSeek V3.2 完成