Bessie's Birthday Party Toy Reuse

Bessie is planning a birthday celebration over \(D\) days. On day \(i\), she needs \(T_i\) toys. She can purchase a new toy from the toy shop at a cost of \(T_c\) dollars; note that the shop disinfects the toy on sale so it is immediately ready for use. However, to save money, Bessie can also reuse toys from previous days if they are disinfected. After a toy is used on some day, it can be disinfected by one of the two available services:

• The first service charges \(C_1\) dollars and takes \(N_1\) nights. That is, if a toy is used on day \(i\) and disinfected via the first service, it will be available on day \(i+N_1\).
• The second service charges \(C_2\) dollars and takes \(N_2\) nights (making the toy available on day \(i+N_2\)).

Each toy can be used once per day; however, once used and disinfected it can be reused on a later day. Note that Farmer John requires every reused toy to be disinfected before the next use. Help Bessie determine the minimum total cost to provide all required toys over the \(D\) days.

Constraints:

• \(1 \le D \le 100000\) (70% of the test data have \(D \le 500\))
• \(1 \le T_i \le 50\)
• \(1 \le T_c \le 60\)
• \(1 \le C_1, C_2 \le 60\)
• \(1 \le N_1, N_2 \le D\)

Hint: One way to solve the problem is to view each toy as a chain of usages. Buying a new toy on the day it is first needed costs \(T_c\) dollars. Reusing a toy requires an additional disinfection cost; for instance, if a toy used on day \(i\) is disinfected by the first service for use on day \(i+N_1\), the extra cost incurred is \(C_1\) dollars. Notice that choosing to reuse is beneficial only if the disinfection cost is less than the cost of buying a new toy (i.e. if \(C_j < T_c\)).

You must output the minimum total cost to supply the toys over all \(D\) days.

inputFormat

The first line contains six space‐separated integers:

D T_c C_1 N_1 C_2 N_2

The next line contains \(D\) space‐separated integers \(T_1, T_2, \ldots, T_D\) representing the number of toys required on each day.

\(\newline\)

outputFormat

Output a single integer: the minimum total cost Bessie must spend to provide the required toys.

sample

3 10 5 1 6 2
2 1 1

30