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$，表示每一关的小怪数量。

无

无

- 对于 $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$ 个关卡结束游戏。 - 如果移动前该关卡里有没有杀死的敌人，回到这个关卡时敌人的状态不会发生变化。