Toy Sterilization

Jungmoon is holding a birthday party for $D$ days. Friends will attend the party, and Jungmoon plans to play with toys every day. On day $i$, exactly $T_i$ toys are needed.

A toy shop sells one toy for $T_c$ won. A toy that has already been used cannot be used again as-is; only a new toy or a toy that has finished sterilization may be used.

Jungmoon can use two sterilization facilities. If a toy is left at the first facility at night, it can be picked up in the morning after $N_1$ days, and the cost is $C_1$ won per toy. If a toy is left at the second facility at night, it can be picked up in the morning after $N_2$ days, and the cost is $C_2$ won per toy.

Jungmoon may buy toys as needed and send used toys to the sterilization facilities. Find the minimum total cost required to complete all party days.

The first line contains six integers $D$, $N_1$, $N_2$, $C_1$, $C_2$, and $T_c$.

Each of the next $D$ lines contains one integer $T_i$, the number of toys needed on day $i$.

Toy Sterilization

Problem

Input

Output

Constraints