题目描述

Bessie's birthday is coming up, and she wishes to celebrate for the next D (1 <= D <= 100,000; 70% of testdata has 1 <= D <= 500) days. Cows have short attention spans so Bessie wants to provide toys to entertain them. She has calculated that she will require T_i (1 <= T_i <= 50) toys on day i.
Bessie's kindergarten provides many services to its aspiring bovine programmers, including a toy shop which sells toys for Tc (1 <= Tc <= 60) dollars. Bessie wishes to save money by reusing toys, but Farmer John is worried about transmitting diseases and requires toys to be disinfected before use. (The toy shop disinfects the toys when it sells them.)
The two disinfectant services near the farm provide handy complete services. The first one charges C1 dollars and requires N1 nights to complete; the second charges C2 dollars and requires N2 nights to complete (1 <= N1 <= D; 1 <= N2 <= D; 1 <= C1 <= 60; 1 <= C2 <= 60). Bessie takes the toys to the disinfecters after the party and can pay and pick them back up the next morning if one night service is rendered, or on later mornings if more nights are required for disinfecting.
Being an educated cow, Bessie has already learned the value of saving her money. Help her find the cheapest way she can provide toys for her party.
POINTS: 400
Bessie的生日快到了，她希望用D（1<=D<=100000）天来庆祝。奶牛们的注意力不会太集中，因此Bessie想通过提供玩具的方式来使它们高兴。她已经计算出了第i天需要的玩具数Ti（1<=Ti<=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已经了解到节约的意义。帮助她找到提供玩具的最便宜的方法。

输入格式：

Line 1: Six space-separated integers: D, N1, N2, C1, C2, Tc
Lines 2..D+1: Line i+1 contains a single integer: T_i

输出格式：

Line 1: The minimum cost to provide safe and sanitary toys for Bessie's birthday parties.

输入样例#1：

4 1 2 2 1 3 
8 
2 
1 
6 

输出样例#1：

35