CF1396C.Monster Invaders

Ziota found a video game called "Monster Invaders".

Similar to every other shooting RPG game, "Monster Invaders" involves killing monsters and bosses with guns.

For the sake of simplicity, we only consider two different types of monsters and three different types of guns.

Namely, the two types of monsters are:

• a normal monster with $1$ hp.
• a boss with $2$ hp.

And the three types of guns are:

• Pistol, deals $1$ hp in damage to one monster, $r_1$ reloading time
• Laser gun, deals $1$ hp in damage to all the monsters in the current level (including the boss), $r_2$ reloading time
• AWP, instantly kills any monster, $r_3$ reloading time

The guns are initially not loaded, and the Ziota can only reload 1 gun at a time.

The levels of the game can be considered as an array $a_1, a_2, \ldots, a_n$, in which the $i$-th stage has $a_i$ normal monsters and 1 boss. Due to the nature of the game, Ziota cannot use the Pistol (the first type of gun) or AWP (the third type of gun) to shoot the boss before killing all of the $a_i$ normal monsters.

If Ziota damages the boss but does not kill it immediately, he is forced to move out of the current level to an arbitrary adjacent level (adjacent levels of level $i$ $(1 \lt i \lt n)$ are levels $i - 1$ and $i + 1$, the only adjacent level of level $1$ is level $2$, the only adjacent level of level $n$ is level $n - 1$). Ziota can also choose to move to an adjacent level at any time. Each move between adjacent levels are managed by portals with $d$ teleportation time.

In order not to disrupt the space-time continuum within the game, it is strictly forbidden to reload or shoot monsters during teleportation.

Ziota starts the game at level 1. The objective of the game is rather simple, to kill all the bosses in all the levels. He is curious about the minimum time to finish the game (assuming it takes no time to shoot the monsters with a loaded gun and Ziota has infinite ammo on all the three guns). Please help him find this value.

齐奥塔发现了一款名为“怪物入侵者”（Monster Invaders）的视频游戏。

与所有其他射击类角色扮演游戏类似，“怪物入侵者”涉及使用枪械击杀怪物和Boss。

为简化问题，我们仅考虑两种类型的怪物和三种类型的枪械：

两种怪物类型为：

• 普通怪物：生命值为 $1$；
• Boss：生命值为 $2$。

三种枪械类型为：

• 手枪（Pistol）：对单个怪物造成 $1$ 点伤害，装填时间为 $r_1$；
• 激光枪（Laser gun）：对当前关卡中所有怪物（包括Boss）各造成 $1$ 点伤害，装填时间为 $r_2$；
• AWP：立即击杀任意一个怪物，装填时间为 $r_3$。

初始时所有枪械均未装填，且齐奥塔每次只能为一把枪装填。

游戏关卡可视为一个数组 $a_1, a_2, \ldots, a_n$，其中第 $i$ 关包含 $a_i$ 只普通怪物和 1 只Boss。由于游戏机制限制，齐奥塔不得在清空该关全部 $a_i$ 只普通怪物之前，用手枪（第一种枪）或AWP（第三种枪）攻击Boss。

若齐奥塔对Boss造成伤害但未能将其立即击杀（即仅削减其 1 点生命值，使其剩余生命值为 1），则他必须立刻离开当前关卡，传送至任意一个相邻关卡（关卡 $i$（其中 $1 < i < n$）的相邻关卡为关卡 $i-1$ 和 $i+1$；关卡 $1$ 的唯一相邻关卡为关卡 $2$；关卡 $n$ 的唯一相邻关卡为关卡 $n-1$）。此外，齐奥塔也可在任意时刻主动选择传送至一个相邻关卡。每次在相邻关卡之间传送均通过传送门完成，耗时为 $d$。

为避免扰乱游戏内的时空连续性，在传送过程中严格禁止装填枪械或射击怪物。

齐奥塔从第 1 关开始游戏。游戏目标非常简单：击杀所有关卡中的所有Boss。他很好奇完成游戏所需的最短时间（假设使用已装填好的枪射击怪物不消耗时间，且三种枪均有无限弹药）。请帮助他求出该最小时间值。

The first line of the input contains five integers separated by single spaces: $n$ $(2 \le n \le 10^6)$ — the number of stages, $r_1, r_2, r_3$ $(1 \le r_1 \le r_2 \le r_3 \le 10^9)$ — the reload time of the three guns respectively, $d$ $(1 \le d \le 10^9)$ — the time of moving between adjacent levels.

The second line of the input contains $n$ integers separated by single spaces $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^6, 1 \le i \le n)$.

输入的第一行包含五个由单个空格分隔的整数：$n$ $(2 \le n \le 10^6)$ —— 关卡数量，$r_1, r_2, r_3$ $(1 \le r_1 \le r_2 \le r_3 \le 10^9)$ —— 三把枪各自的装弹时间，$d$ $(1 \le d \le 10^9)$ —— 在相邻关卡之间移动所需的时间。

输入的第二行包含 $n$ 个由单个空格分隔的整数 $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^6, 1 \le i \le n)$。

Print one integer, the minimum time to finish the game.

输出一个整数，表示完成游戏所需的最短时间。

In the first test case, the optimal strategy is:

• Use the pistol to kill three normal monsters and AWP to kill the boss (Total time $1\cdot3+4=7$)
• Move to stage two (Total time $7+3=10$)
• Use the pistol twice and AWP to kill the boss (Total time $10+1\cdot2+4=16$)
• Move to stage three (Total time $16+3=19$)
• Use the laser gun and forced to move to either stage four or two, here we move to stage four (Total time $19+3+3=25$)
• Use the pistol once, use AWP to kill the boss (Total time $25+1\cdot1+4=30$)
• Move back to stage three (Total time $30+3=33$)
• Kill the boss at stage three with the pistol (Total time $33+1=34$)

Note that here, we do not finish at level $n$, but when all the bosses are killed.

在第一个测试用例中，最优策略为：

• 使用手枪击杀三只普通怪物，并使用AWP击杀Boss（总耗时 $1\cdot3+4=7$）
• 移动至第二关（总耗时 $7+3=10$）
• 使用手枪两次，并使用AWP击杀Boss（总耗时 $10+1\cdot2+4=16$）
• 移动至第三关（总耗时 $16+3=19$）
• 使用激光枪，并被迫移动至第四关或第二关；此处选择移动至第四关（总耗时 $19+3+3=25$）
• 使用手枪一次，并使用AWP击杀Boss（总耗时 $25+1\cdot1+4=30$）
• 返回第三关（总耗时 $30+3=33$）
• 使用手枪击杀第三关的Boss（总耗时 $33+1=34$）

注意：此处我们并非在第 $n$ 关结束游戏，而是在所有Boss均被击杀时结束。