D. 水龙
每个测试点时间限制：$3$ 秒
每个测试点内存限制：$1024$ 兆字节

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

你还有一条龙陪伴。它有一个非负整数表示的体力值。龙的体力用于执行游泳和飞行能力。初始时，它的体力为 $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 \le N \le 200000$；$1 \le D, T_s, T_f, T_w \le 200000$）。
第二行包含 $N$ 个整数 $P_i$（$1 \le P_i \le 200000$）。

输出
输出一行一个整数，表示带着龙到达岛屿 $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$。
• 与龙一起飞到岛屿 $2$。岛屿 $2$ 的神社将龙的体力增加到 $2$。
• 独自步行到岛屿 $3$。岛屿 $3$ 的神社将龙的体力增加到 $6$。
• 独自步行到岛屿 $4$。岛屿 $4$ 的神社将龙的体力增加到 $8$。
• 独自步行到岛屿 $3$。
• 独自步行到岛屿 $2$。
• 与龙一起游到岛屿 $3$。龙的体力变为 $4$。
• 与龙一起游到岛屿 $4$。龙的体力变为 $0$。
• 独自步行到岛屿 $5$。岛屿 $5$ 的神社将龙的体力增加到 $1$。
• 独自步行到岛屿 $4$。
• 与龙一起飞到岛屿 $5$。

对于样例 #2：
对每个 $1 \le i < 5$ 重复以下过程：岛屿 $i$ 的神社增加龙的体力，然后使用该体力与龙一起飞到岛屿 $i+1$。