Description

A traveler wants to drive a car from one city to another at the minimum cost (assume the fuel tank is empty at the start). Given the distance between the two cities $S$, the fuel tank capacity $C$ (in liters), the distance per liter $L$, the price per liter at the starting point $P_0$, and the number of gas stations along the route $N$, as well as the distance from the starting point to gas station $i$, $D_i$, and the price per liter at gas station $i$, $P_i\ (i=1,2,\dots,N)$, you need to find the minimum cost.

Input Format

The first line contains four real numbers $S, C, L, P_0$ and one integer $N$, as described above.

For each of the next $N$ lines, the $(i+1)$-th line contains two real numbers $D_i$ and $P_i$, as described above.

Output Format

Print a single real number, the minimum cost (rounded to two decimal places).

If it is impossible to reach the destination, output No Solution.

275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2

26.95

Hint

Constraints: $0 \leq N \leq 6$, $0 \leq D_i \leq S$, $0 \leq S, C, L, P_0, P_i \leq 500$.

NOIP 1999 Junior problem 3, Senior problem 3.

Translated by ChatGPT 5