405096: GYM101790 F MK Ultra

N Unidentified Flying Saucers has arrived in "MK Ultra" spaceport. To identify saucers, they must first be washed. All saucers are arranged in the stack in particular order. The height of the i-th saucer from the top of the stack is H_i.

There are two washing machines in the spaceport. It is allowed to load several consequent saucers from the top of the stack to a washing machine if and only if this washing machine is free. The height of the buffer of the first washing machine is D₁, and the height of the buffer of the second one is D₂. It is impossible to load saucers in the buffer with a total height greater than the height of the corresponding buffer. If at some point of time both machines are free, they can perform loading in any order, but each loading operation should be atomic.

While there are flying saucers in the washing machine buffer, it pulls out and wash them one at a time. While all saucers from the buffer are not washed, the machine is considered busy. Washed saucers are sent for identification and are not involved in the washing process any more. The first machine washes saucer with height H_i for S₁ × H_i seconds, and the second one washes it for S₂ × H_i seconds.

Determine the minimum period of time needed to wash all flying saucers. The time for all processes except for directly washing saucers by wasing machines can be neglected. If necessary, the machines can stand idle for a while, if this minimizes the final result.

The first line contains two integers S₁ and S₂ (1 ≤ S₁, S₂ ≤ 50).

The second line contains two integers D₁ and D₂ (1 ≤ D₁, D₂ ≤ 10000). It is guaranteed that any saucer can be washed in any washing machine.

The third line contains the number of flying saucers in the initial stack N (1 ≤ N ≤ 200).

The last line contains N integers H_i (1 ≤ H_i ≤ 50), denoting the heights of the saucers, starting from the top of the stack.

Print single integer: the minimum number of seconds from the beginning of the washing until the moment when all flying saucers are sent for identification.

4 3
14 11
10
1 2 3 9 5 2 7 3 2 8

72

In the example, the minimum time could be achieved as follows:

• at time 0 the first machine loads saucer 1, the second loads 2;
• at time 4 the first machine loads saucer 3;
• at time 6, the second machine loads saucer 4;
• at the time 16 the first machine loads saucers 5 - 7;
• at time 33 the second machine loads saucers 8 - 9;
• at time 48, the second machine loads saucer 10.