Description

A travel agent in the United States is often asked to estimate the minimum cost of driving from one city to another. He has a list of most gas stations on the usual route. The list includes the location of each station and the current price per gallon of gasoline.

To simplify the estimation, the agent uses the following simplified rules for driver behavior:

• Unless the car cannot reach the next gas station (if any) or the destination with the gasoline currently in the tank, the driver will never stop at a station if the tank has at least half of its maximum capacity remaining.
• At every stop, the driver always fills the tank to full.
• After stopping at a gas station, the driver spends $2.00$ yuan on fast food and candy for the trip.
• When heading to a gas station or the destination, the driver does not need to carry more gasoline than necessary. No "safety margin" is required.
• The driver always starts the trip with a full tank.
• Each payment at a gas station is rounded to the nearest cent ($1$ yuan equals $100$ cents).

You must write a program to estimate the minimum amount of money the driver will have to pay for gasoline and food on the trip.

Input Format

The first $2$ lines give the information about the origin and the destination. The subsequent lines represent gas stations on the route, one per line. Below is the exact format of the input items and their meaning.

First line: one real number — the distance from the origin to the destination (miles).

Second line: three real numbers and one integer:

• The first real number is the maximum capacity of the car’s gas tank (gallons).
• The second real number is the car’s fuel efficiency, in miles per gallon (mpg).
• The third real number is the cost to fill the tank in the origin city (yuan).
• The last integer is the number of gas stations on the route $n$.

Each of the next $n$ lines contains two real numbers:

• The first real number is the distance from the origin to the gas station (miles).
• The second real number is the station’s price per gallon (cents).

All numbers in the input are positive. The gas stations on a route are ordered by increasing distance from the origin. There is no station whose distance from the origin exceeds the total distance to the destination. The stations on each route are arranged appropriately so that any car can drive from the origin to the destination.

Output Format

A single line with one real number (rounded to two decimal places), representing the minimum total cost (yuan).

475.6
11.9 27.4 14.98 6
102.0 99.9
220.0 132.9
256.3 147.9
275.0 102.9
277.6 112.9
381.8 100.9

27.31

Hint

Constraints

For all testdata, $n \le 51$.

Translated by ChatGPT 5