Ziota 发现了一款名为“Monster Invaders”的视频游戏。
与其他射击角色扮演游戏类似,《怪物入侵者》涉及用枪杀死怪物和头目。
为了简单起见,我们只考虑两种不同类型的怪物和三种不同类型的枪支。
也就是说,这两种怪物是:
- 一个拥有 $$$1$$$ hp 的普通怪物。
- 拥有 $$$2$$$ hp 的 Boss。
这三种枪是:
- 手枪,对一只怪物造成 $$$1$$$ hp 伤害,装弹时间 $$$r_1$$$
- 激光枪,对当前关卡中的所有怪物(包括首领)造成 $$$1$$$ hp 伤害,$$$r_2$$$ 装弹时间
- AWP,立即杀死任何怪物,$$$r_3$$$ 重新加载时间
枪支最初未装填,并且 Ziota 一次只能重新装填 1 支枪。
游戏的关卡可以被认为是一个数组$$$a_1,a_2,\ldots,a_n$$$,其中第$$$i$$$级有$$$a_i$$$普通怪物和1个boss。由于游戏的性质,齐奥塔在杀死所有 $$$a_i$$$ 普通怪物之前无法使用手枪(第一种枪)或 AWP(第三种枪)射击 Boss。
如果 Ziota 伤害了 Boss 但没有立即杀死它,他将被迫离开当前关卡到任意相邻关卡($$$i$$$ $$$(1 < i < n)$$$ 关卡的相邻关卡为 $$$i - 1$$$ 和 $$$i + 1$$$,$$$1$$$ 关卡的唯一相邻关卡是 $$$2$$$ 关卡,唯一相邻的关卡为 $$$2$$$。级别 $$$n$$$ 的级别是级别 $$$n - 1$$$)。齐奥塔还可以随时选择移动到相邻级别。相邻关卡之间的每次移动均由门户管理,传送时间为$$$d$$$。
为了不破坏游戏内的时空连续体,严禁在传送过程中重新装弹或射击怪物。
Ziota 从第 1 级开始游戏。游戏的目标相当简单,杀死所有级别中的所有 Boss。他很好奇完成游戏的最短时间(假设用上膛的枪射击怪物不需要时间,并且齐奥塔的三把枪都有无限弹药)。请帮他找到这个值。
输入
输入的第一行包含五个由单个空格分隔的整数: $$$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)$$$。
输出
打印一个整数,完成游戏的最短时间。
示例
输入 #1
4 1 3 4 3 3 2 5 1
输出 #1
34
输入 #2
4 2 4 4 1 4 5 1 2
输出 #2
31
注意
在第一个测试用例中,最优策略是:
- 使用手枪杀死三个普通怪物并用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 都被杀死时结束。