#1089. 2-02D. MTC的salt&vinegar薯片

内存限制:512 MiB 时间限制:1125 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Akatsuki

题目描述

MTC每天早上9:00要从university residence走到university上学,由于起的太迟没有准备早饭,路上她需要吃salt&vinegar薯片补充能量(出发时她没有薯片)。

给定residence到university之间的距离 l1l1 ,MTC的胃容量 cc(以克为单位,MTC胃里的薯片不能超过c),每克薯片能支持的走路距离 l2l2,出发点的零食店每克薯片价格 p0p0 和沿途零食店数 nnnn 可以为零),第 ii 个零食店离出发点的距离 didi、零食店每克薯片价格 pipi(i=1,2,…,n)。

MTC想知道到达university所需的最小花销,计算结果四舍五入至小数点后两位。

输入格式

第一行五个数,l1l1ccl2l2p0p0nn

接下来有n行,每行两个数字,零食店i离出发点的距离 didi 和每克薯片价格 pipi。(不一定按离出发点的距离升序给出)

输出格式

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

样例

样例输入

275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2

样例输出

26.95

数据范围与提示

0c,l1,l2,p0,di,pi51060 \le c,l1,l2,p0,di,pi \le 5*10^6

0n2.51060 \le n \le 2.5*10^6, 0nl10 \le n \le l1