CF1396C Monster Invaders

这是一个 RPG 枪战游戏。 有 $n$ 个关卡，每一个关卡都有 $a_i$ 个生命值为 $1$ 的小怪，$1$ 个生命值为 $2$ 的 boss。 有三种武器： + 手枪，可以对一个怪物造成 $1$ 点伤害，每次使用前需要 $r_{1}$ 秒装弹。 + 激光枪，可以对目前关卡所有怪物造成 $1$ 点伤害，每次使用前需要 $r_{2}$ 秒装弹。 + AWP（一种狙击枪），可以直接杀死任意怪物，每次使用前需要 $r_{3}$ 秒装弹。 由于游戏 $feature$，用手枪或 AWP 攻击 boss 前必须先杀死 boss 所在关卡的所有小怪。如果攻击 boss 但此次攻击并没有杀死 boss，必须移动到该关卡的相邻关卡。 除此之外，可以在任意时间移动到所在关卡的相邻关卡，每一次移动需要 $d$ 秒，此时什么都不能做。 从第一关开始游戏，游戏目标是击杀所有 boss，求完成游戏的最短时间。 第二行 $n$ 个正整数 $a_1,a_2,\dots,a_n$，表示每一关的小怪数量。

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) $ .

一行一个正整数，表示最短通关时间。

- 对于 $100\%$ 的数据，$2\leq n\leq 10^6,1\leq r1\leq r2\leq r3\leq 10^9,1\leq d\leq 10^9,1\leq a_i\leq 10^6$ - 不要求在第 $n$ 个关卡结束游戏。 - 如果移动前该关卡里有没有杀死的敌人，回到这个关卡时敌人的状态不会发生变化。