2007. [USACO Nov08]玩具

【题目描述】

Bessie的生日快到了，她希望用$D（1<=D<=100000）$天来庆祝。奶牛们的注意力不会太集中，因此Bessie想通过提供玩具的方式来使它们高兴。她已经计算出了第$i$天需要的玩具数$T_i（1<=T_i<=50）$.

Bessie的幼儿园给它们的奶牛程序员们提供了许多服务，包括一个每天以$Tc(1<=Tc<=60)$美元卖出商品的玩具店。Bessie想尽可能地节省钱。但是Farmer John担心没有经过消毒的玩具会带来传染病。（玩具店卖出的玩具是经过消毒）

有两种消毒的方式。第1种方式需要收费$C1$美元，需要$N1$个晚上的时间；第2种方式需要收费$C2$美元，需要$N2$个晚上的时间$（1<=N1,N2<=D；1<=C1,C2<=60）$。Bessie在派对结束之后把她的玩具带去消毒。如果消毒只需要一天，那么第二天就可以拿到；如果还需要一天，那么第三天才可以拿到。

作为一个受过教育的奶牛，Bessie已经了解到节约的意义。帮助她找到提供玩具的最便宜的方法。

【输入格式】

第1行：六个用空格隔开的整数$D,N1,N2,C1,C2,Tc。$

第2到D+1行：第i+1行包含一个整数$T_i$。

【输出格式】

提供玩具所需要的最小费用。

【样例输入】

4 1 2 2 1 3
8
2
1
6

【样例输出】

35

【提示】

第1天：买8个玩具，花去$24；送2个玩具去快洗，6个慢洗。

第2天：取回2个快洗的玩具，花去$4.送1个玩具去慢洗。

第3天：取回6个慢洗的玩具，花去$6.

第4天：取回所有的玩具，与现有的加在一起正好6个，花去$1。这样就用了最少的钱。

【来源】

Chen Hu, 2006

Translation by Wentai Zhang