MTC每天早上9:00要从university residence走到university上学,由于起的太迟没有准备早饭,路上她需要吃salt&vinegar薯片补充能量(出发时她没有薯片)。
给定residence到university之间的距离 l1l1l1 ,MTC的胃容量 ccc(以克为单位,MTC胃里的薯片不能超过c),每克薯片能支持的走路距离 l2l2l2,出发点的零食店每克薯片价格 p0p0p0 和沿途零食店数 nnn( nnn 可以为零),第 iii 个零食店离出发点的距离 dididi、零食店每克薯片价格 pipipi(i=1,2,…,n)。
MTC想知道到达university所需的最小花销,计算结果四舍五入至小数点后两位。
第一行五个数,l1l1l1,ccc,l2l2l2,p0p0p0,nnn
接下来有n行,每行两个数字,零食店i离出发点的距离 dididi 和每克薯片价格 pipipi。(不一定按离出发点的距离升序给出)
一个数,表示最小花销,计算结果四舍五入至小数点后两位。如果无法到达目的地,则输出“No Solution”。
275.6 11.9 27.4 2.8 2 102.0 2.9 220.0 2.2
26.95
0≤c,l1,l2,p0,di,pi≤5∗1060 \le c,l1,l2,p0,di,pi \le 5*10^60≤c,l1,l2,p0,di,pi≤5∗106
0≤n≤2.5∗1060 \le n \le 2.5*10^60≤n≤2.5∗106, 0≤n≤l10 \le n \le l10≤n≤l1