Minimum Fuel Cost

A traveler wishes to drive a car from one city to another with the minimum possible cost. The car starts with an empty fuel tank. You are given the following information:

• The distance between the two cities: \(D_1\) (in kilometers).
• The capacity of the car’s fuel tank: \(C\) (in liters).
• The distance that can be driven per liter of gasoline: \(D_2\) (in kilometers per liter).
• The price per liter of gasoline at the starting point: \(P\).
• The number of gas stations along the route: \(N\) (which can be zero).
• For each gas station \(i\) (\(i=1,2,\dots,N\)): the distance from the starting city \(D_i\) (in kilometers) and its gasoline price per liter \(P_i\).

Your task is to compute the minimum cost required to travel from the starting city to the destination. You may refuel at the starting city and at any gas station along the way. The car starts with no fuel; hence, the initial fueling is mandatory. If it is impossible to reach the destination, output No Solution. Otherwise, output the cost rounded to two decimal places.

Note: When writing any formulas in your solution, use LaTeX format. For example, the fuel required to cover a distance \(d\) kilometers is given by \(\frac{d}{D_2}\).

inputFormat

The input is given in the following format:

D1 C D2 P N
D1_1 P1_1
D1_2 P1_2
... 
D1_N P1_N

Where:

• The first line contains five numbers: \(D_1\) (destination distance), \(C\) (fuel tank capacity), \(D_2\) (distance per liter), \(P\) (price at starting city) and \(N\) (number of gas stations).
• Each of the next \(N\) lines contains two numbers: \(D_i\) (distance from the starting point) and \(P_i\) (price at the \(i\)th gas station), for \(i=1,2,\ldots,N\).

outputFormat

If the destination can be reached, output the minimum cost rounded to two decimal places. Otherwise, output No Solution.

sample

500 50 10 1.2 4
100 1.3
150 1.1
300 1.5
450 1.0

56.00