你居住在一个由 $N$ 个岛屿（编号从 1 到 $N$）组成的群岛上，这些岛屿排成一行。对于 $1 \le i < N$，岛屿 $i$ 与岛屿 $i+1$ 相邻。在相邻的岛屿 $i$ 和 $i+1$ 之间，有一对单向水下隧道：一条允许你从岛屿 $i$ 走到岛屿 $i+1$，另一条则用于相反方向。每条隧道最多只能使用一次。

你还带着一条龙。它拥有一个由非负整数表示的体力值。龙执行其能力（游泳和飞行）需要消耗体力。初始时，它的体力为 0。

龙的体力可以通过以下方式增加：每个岛屿 $i$ 上都有一个魔法神龛，当你第一次访问岛屿 $i$ 时，它会立即增加你龙的体力 $P_i$（无论龙当前在什么位置）。此事件不消耗时间。

当你身处某个岛屿时，可以执行以下 3 种移动方式：

• 与龙一起游泳：如果龙和你都在同一个岛屿上，你可以游向相邻的岛屿。前提是龙的体力至少为 $D$。此移动会减少龙 $D$ 点体力，并耗时 $T_s$ 秒。
• 与龙一起飞行：如果龙和你都在同一个岛屿上，你可以飞向相邻的岛屿。前提是龙的体力不为 0。此移动会将龙的体力归零，并耗时 $T_f$ 秒。
• 独自步行：不带龙，通过水下隧道走到相邻的岛屿。此移动耗时 $T_w$ 秒。一旦你通过这条隧道，它就不能再次使用。

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

你和你的龙目前都在岛屿 1。你的任务是带着龙到达岛屿 $N$。请确定完成任务所需的最短时间。

输入格式

第一行包含五个整数 $N$、$D$、$T_s$、$T_f$、$T_w$ ($2 \le N \le 200\,000$; $1 \le D, T_s, T_f, T_w \le 200\,000$)。 第二行包含 $N$ 个整数 $P_i$ ($1 \le P_i \le 200\,000$)。

输出格式

输出一行一个整数，表示带着龙到达岛屿 $N$ 所需的最短时间。

样例

输入 1

5 4 2 9 1
1 2 4 2 1

输出 1

28

说明 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

5 4 2 1 1
1 2 4 2 1

输出 2

4

说明 2

对于 $1 \le i < 5$ 重复以下过程：岛屿 $i$ 的神龛增加龙的体力，然后使用体力与龙一起飞往岛屿 $i + 1$。

输入 3

3 4 2 10 1
3 1 2

输出 3

16