NOIP '99 P3 - Traveller's Budget

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

A traveller wants to drive from one city to another with minimum cost (assuming the gas tank is empty at the beginning). Given the distance between two cities is D_1, the capacity of the car's fuel tank is C (in litres), the distance that a litre of gasoline can travel is D_2, the gas price per litre at the starting point is P, and there are N gas stations along the way, the distance from the gas station i to the starting point is D_i, and the price of gasoline per litre is P_i (i = 1, 2, \dots, N). Round your answer to two decimal places. If the destination cannot be reached, output No Solution.

Constraints

1 \le N \le 6

1 \le D_1, C, D_2, P, P_i, D_i \le 500

Input Specification

The first line contains five space-separated numbers, representing D_1, C, D_2, P and N, respectively.

The next N lines contain two numbers D_i, the distance from the starting point to the gas station i, and P_i, the price of gasoline per litre at the gas station i.

Output Specification

Output the minimum cost required, rounded to two decimal places. If the destination cannot be reached, output No Solution.

Sample Input

275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2

Sample Output

26.95

Problem translated to English by Tommy_Shan.


Comments

There are no comments at the moment.