P1016 [NOIP 1999 Junior/Senior] Traveler's Budget

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.

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.

Print a single real number, the minimum cost (rounded to two decimal places). If it is impossible to reach the destination, output `No Solution`.

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