AIOC Banner

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.

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

30000
1 100
870
6
450
750
1200
1740
1800
2250

Sample Output

92250

Scoring

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

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 25 May 2019, 12:22am AEST