Problem: Belts

Want to try solving this problem? You can submit your code online if you log in or register.

Belts

Time Limit: 0.02 seconds
Memory Limit: 30 Mb

It's fashion week, and you are trying on the latest designer belts from Paris. Unfortunately none of the belts fit you, which can mean only one thing. You need more exercise.

You decide the best time to exercise is during your tram ride home. The tram runs in a straight line from school to home, and there are several stops on this line. You can get some exercise by hopping off the tram at some stop, walking to another stop further down the line, and then hopping onto the next tram that comes by. You can do this as many times as you like (tram, walk, tram, walk and so on). You may choose to start the journey walking if you wish, and you may choose to hop off a tram at some point and walk the rest of the way home.

Trams run every t minutes, with the first tram leaving school precisely when you begin your journey. Trams move at a fixed speed, and you walk at a slower fixed speed. You may only walk forwards — you may not walk backwards or walk around in circles. If you are walking from stop a to stop b and catching the next tram, you simply wait at stop b and listen to your mp3 player until the next tram comes along. If you arrive at stop b at precisely the same moment as a tram comes past, you may hop on board.

After poring through a handful of health magazines, you decide that you need to walk at least k metres during your travels home. Your task is to find the shortest possible travel time from start to finish that meets this requirement.

Constraints

All times below are measured in milliseconds, and all distances are measured in metres.

30,000 <= t <= 1,000,000, where t is the time between each tram and the next;
1 <= mt < mw <= 100, where mt is the time it takes a tram to move one metre and mw is the time it takes you to walk one metre;
1 <= k <= 10,000, where k is minimum distance that you must walk;
1 <= s <= 100, where s is the total number of tram stops (excluding the school where your journey begins);
No two adjacent tram stops are more than 1,000 metres apart;
The last stop is at least k metres from the school (i.e., it is possible to actually get the exercise that you need).

Furthermore, for 60% of the available marks, the minimum walking distance will satisfy k <= 2,000.

Example

Consider the tram line illustrated below. It begins with the school on the left hand side, after which come s=6 tram stops. Distances between consecutive stops are marked on the diagram, and your house is at the very last stop.

Suppose that the council is extremely efficient, and that trams run every 30 seconds, i.e., every t=30,000 milliseconds. Trams take mt=1 millisecond to move one metre, and you take a brisk mw=100 milliseconds to walk one metre. Your fitness regime requires you to walk at least k=870 metres during your journey.

An optimal strategy for getting home is as follows.

Action	Stops	Distance	Time
Tram	School–1	450m	450ms
Walk	1–2	300m	30,000ms
Wait for tram	2		300ms
Tram	2–3	450m	450ms
Walk	3–5	600m	60,000ms
Wait for tram	5		600ms
Tram	5–6	450m	450ms
Total			92,250ms

Your total walking distance according to this plan is 900m, which is enough since it is more than the required k=870m. The total travel time is 92,250 milliseconds.

Input

Your program must read from standard input. The first line will contain the single integer t, giving the time between each tram and the next. The second line will contain the two integers mt and mw separated by a single space, giving the time it takes a tram to move one metre and the time it takes you to walk one metre. The third line will contain the single integer k, giving the minimum distance that you need to walk.

The fourth line of input will contain the single integer s, giving the total number of tram stops (excluding the school where the journey begins). Following this will be s lines, giving the positions of the individual stops in consecutive order from school to home. The ith of these lines will contain the integer di, giving the distance from the school to the ith stop. Your house is at the last of these stops.

Once more, all times are measured in milliseconds and all distances are measured in metres.

Output

Your program must write a single line to standard output. This line must contain a single integer giving the shortest time possible for the entire journey, measured in milliseconds.

Sample Input

Sample Output

Scoring

The score for each input scenario will be 100% if the correct answer is output, or 0% otherwise.