Start: Jun, 10, 2015 13:00:00
周赛Round#9 DP专场
End: Jun, 10, 2015 17:00:00
Time elapsed:
Time remaining:

旅行家的预算 1627

Time Limit:  1 s      Memory Limit:   32 MB
Submission:12     AC:1     Score:1

Description

 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。给定两个城市之间的距离D1、汽车油箱的容量C(以升为单位)、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数NN可以为零),油站i离出发点的距离Di、每升汽油价格Pii=1,2,……,N)。计算结果四舍五入至小数点后两位。如果无法到达目的地,则输出“No Solution”。

Input

第一行是五个数依次为:D1  C  D P  N。

接下来有N行,每行包含两个数DiPi。

(其中只有N是正整数,其余均为正实数。C和N小于100,其余输入均小于1000。)

Output

最少费用。

Samples

input
275.6 11.9 27.4 2.8 2 102.0 2.9 220.0 2.2
output
26.95