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.

题目描述

小北迷恋上了一款名为王者毒药的游戏，在游戏的某个副本任务中，小北需要击败排成一列的 $n$ 个敌人，第 $i$ 个敌人拥有 $h_i$ 的血量。

当小北的一次攻击使得敌人的血量被降到小于等于 0 时，这个敌人就会死亡，在该敌人身后的其他敌人会向前补齐空位。在游戏开始时，第 1 个敌人站在最前。

在王者毒药中，小北只有以下五种技能可以使用：

1. 消耗 $m_A$ 的法力值，对当前第一个敌人造成 $d_A$ 的伤害。
2. 消耗 $m_B$ 的法力值，对当前第二个敌人造成 $d_B$ 的伤害。
3. 消耗 $m_C$ 的法力值，对当前第三个敌人造成 $d_C$ 的伤害。
4. 消耗 $m_D$ 的法力值，对当前第四个敌人造成 $d_D$ 的伤害。
5. 消耗 $m_E$ 的法力值，对当前的前四个敌人各造成 $40000$ 的伤害。

那么 小北最少需要多少法力值才能击败所有敌人呢？

输入格式

第一行十个整数，$n, d_A, d_B, d_C, d_D, m_A, m_B, m_C, m_D, m_E$，含义如题所示。

第二行 $n$ 个整数，$h_1, h_2, \cdots, h_n$，表示每个敌人的血量。

输出格式

一行一个整数，表示答案。

样例

样例输入 1

3 5000 3000 10000 15000 14 12 20 28 80
4000 6400 4000

样例输出 1

54

数据范围

• 对于 $20 \%$ 的数据，$n \leq 4$。
• 对于 $40 \%$ 的数据，$n \leq 8$。
• 对于 $80 \%$ 的数据，$n \leq 12$。
• 对于 $100 \%$ 的数据，$1 \leq n \leq 20,1 \leq d_A, d_B, d_C, d_D \leq 20000,1 \leq m_A, m_B, m_C, m_D, m_E \leq500,1 \leq h_i \leq 100000$。