You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

枪战地牢

题目描述

这是一个 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,r_1,r_2,r_3,d$，意义见题目描述。 第二行 $n$ 个正整数 $a_1,a_2,\dots,a_n$，表示每一关的小怪数量。

输出格式

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

样例

Input 1

4 1 3 4 3
3 2 5 1

Output 1

34

Input 2

4 2 4 4 1
4 5 1 2

Output 2

31

提示说明

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

Constraints