题目描述

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。给定两个城市之间的距离 $D$、汽车油箱的容量 $C$(以升为单位)、每升汽油能行使距离 $D_0$ 、出发点的每升汽油价格 $P$ 和沿途加油站数 $N$($N$ 可以是 $0$)、加油站 $i$ 离出发点的距离 $D_i$、加油站 $i$ 每升汽油价格 $P_i(i=1,2,3,..., N)$。编程找出一种加油方案，使费用最少，输出这个最少的费用值。

输入格式

第 $1$ 行 $4$ 个实数，依次为 $D、C、D_0$ 和 $P$。 第 $2$ 行为 $n(n < 100)$。 以下的 $n$ 行，每行为一个加油站信息，包括 $2$ 个实数 $D_i$ 和 $P_i$。

输出格式

一行一个实数，表示最小费用，计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。

样例

输入#1

275.60 11.90 27.40 2.80
2
102.00 2.90
220.00 2.20

输出#1

26.95

数据范围/约定

时间空间限制：1s, 256MB.

题目来源

课课通 P9-8-T5