Bessie's birthday is coming up, and she wishes to celebrate for the next ~D~ days. Cows have short attention spans so Bessie wants to provide toys to entertain them. She has calculated that she will require ~T_i~ toys on day ~i~.

Bessie's kindergarten provides many services to its aspiring bovine programmers, including a toy shop which sells toys for ~Tc~ 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. 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.

Constraints

For all subtasks:

~1 \le D \le 100\,000~

~1 \le T_i \le 50~

~1 \le Tc, C1, C2 \le 60~

~1 \le N1, N2 \le D~

Subtask 1 [70%]

~1 \le D \le 500~

Subtask 2 [30%]

No additional constraints.

Input Specification

• Line ~1~: Six space-separated integers: ~D, N1, N2, C1, C2, Tc~

• Lines ~2 \dots D+1~: Line ~i+1~ contains a single integer: ~T_i~

Output Specification

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

Sample Input

4 1 2 2 1 3
8
2
1
6

Explanation for Sample Input

Bessie wishes to party for 4 days, and requires 8 toys the first day, 2 toys the second, 1 toy the third, and 6 toys on the fourth day. The first disinfectant service takes 1 day and charges $2, and the second takes 2 days and charges $1. Buying a new toy costs $3.

Sample Output

35

Explanation for Sample Output

Day 1: Purchase 8 toys in the morning for $24; party in the afternoon. Take 2 toys to the fast cleaner (overnight) and the other 6 toys to the slow cleaner (two nights).

Day 2: Pick up the two toys at the fast cleaner; pay $4. Party in the afternoon. Take 1 toy to the slow cleaner.

Day 3: Pick up 6 toys from the slow cleaner and pay $6. Party in the afternoon.

Day 4: Pick up the final remaining toy from the slow cleaner (bringing the number of toys onsite back to 6); pay $1. Party hearty with the realization that a minimum amount of money was spent.