说明

你生活在一个由 $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$ 所需的最短可能时间。

5 4 2 9 1
1 2 4 2 1

28

5 4 2 1 1
1 2 4 2 1

4

3 4 2 10 1
3 1 2

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$。

翻译由 DeepSeek V3.2 完成