题目描述

$\red{Bessie}$的生日快到了, 她希望用$\red{D (1 <= D <= 100,000}$; $\red{70\%}$的测试数据都满足 $\red{1 <= D <= 500)}$天来庆祝. 奶牛们的注意力不会太集中, 因此$\red{Bessie}$想通过提供玩具的方 式来使它们高兴. 她已经计算出了第$\red{i}$天需要的玩具数$\red{T_i (1 <= T_i <= 50). Bessie}$的幼儿园提供了许多服务给它们的奶牛程序员们, 包括一个每天以$\red{Tc (1 <= Tc <= 60)}$美元卖出商品的玩具店.

$\red{Bessie}$想旧能的节省钱, 但是$\red{Farmer John}$担心没有经过消毒的玩具会带来传染病玩具店卖出的玩具是经过消毒的。有两种消毒的方式. 第$\red{1}$种方式需要收费$\red{C1}$美元, 需要$\red{N1}$个晚上的时间; 第$\red{2}$种方式需要收费 $\red{C2}$美元, 需要$\red{N2}$个晚上的时间$\red{(1 <= N1 <= D}$; $\red{1 <= N2 <= D}$; $\red{1 <= C1 <= 60}$; $\red{1 <= C2 <= 60). }$

$\red{Bessie}$在$\red{party}$结束之后把她的玩具带去消毒. 如果消毒只需要一天, 那么第二天就可以拿到; 如果还需要一天, 那么第三天才可以拿到. 作为一个受过教育的奶牛, $\red{Bessie}$已经了解到节约的意义. 帮助她找到提供玩具的最便宜的方法.

输入格式

第 $\red{1 }$行: 六个用空格隔开的整数 $\red{D, N1, N2, C1, C2, Tc}$

第 $\red{2..D+1 }$行: 第 $\red{i+1 }$行包含一个整数: $\red{T_i}$

输出格式

第 $\red{1 }$行: 提供玩具所需要的最小费用.

样例

输入样例

4 1 2 2 1 3
8
2
1
6

输出样例

35

提示

输入解释:

$\red{Bessie}$想开$\red{4}$天的$\red{party, }$

第$\red{1}$天需要$\red{8}$个玩具,

第$\red{2}$天需要$\red{2}$个玩具,

第$\red{3}$天需要$\red{1}$个玩具,

第$\red{4}$天需要$\red{6}$个玩具.

第一种方式需要$\red{2, }$用时$\red{1}$天;

第二种方式需要$\red{1, }$用时$\red{2}$天. 买一个玩具需要$\red{3.}$

输出解释:

第 $\red{1 }$天 买$\red{8}$个玩具, 花去$\red{24}$; 送$\red{2}$个玩具去快洗, $\red{6}$个慢洗.

第 $\red{2 }$天 取回$\red{2}$个快洗的玩具, 花去$\red{4. }$送$\red{1}$个玩具去慢洗.

第 $\red{3 }$天 取回$\red{6}$个慢洗的玩具, 花去$\red{6.}$

第 $\red{4 }$天 取回所有的玩具与现有的加在一起正好$\red{6}$个), 花去$\red{1. }$这样就用了最少的钱.