// A1033 To Fill or Not to Fill (25分).cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
/*
题意：
1、给油箱（不超过100），杭州跟目的城市距离（不超3万），每加仑能跑的路（小于500），总共加油站几个(小于500）
2、N行，油价每加仑，加油站离杭州的距离
找出最便宜（假设油箱一开始为空，
如果没法到达，打印blabla,
注意精确到小数点后两位
其实不限哪条路对吧，就是求花最少钱，能跑最远就行了！
正确解题：
1、把终点视为单位油价为0，离起点距离为D的加油站，所有加油站按距离从小到大排序。
2、排序完毕后，如果例起点最近加油站的距离不是0，则表示汽车无法触发，输出"THE MAX"
如果离起点最近的加油站距离为0，则进入步骤3
3、假设当前所处的加油站编号为now,接下来从漫游状态下能到达的所有加油站中选出下一个前往的加油站，策略如下：
（1）寻找距离当前加油最近的油价低于单签油价的加油站*（记为k），加恰好能够到达加油站K的油，然后前往加油站k(即优前往更低油价的加油站
（2）如果找不到油价低于当前油价的加油站，则寻找油价最低的，在当前油站加满油，然后前往加油站K（即没有更低油价的，前往尽可能低的油价）
（3）在满油状态下都找不到能到达的加油站，则最远能到达的得距离为当前加油站的距离加上漫游状态下能前进的距离，结束算法
解题：（）
1、估算加满能跑的路程是多少
2、钱ans,一开始肯定找出距离0，加满，
中断的条件是是否超过最远距离
排序，便宜，距离近的，
判断能否到达，能就去这里，还要判断油箱用了多少
不能就下一个
3、估算出能跑的距离，然后找出最便宜的，到哪里，加满，一直这样循环，直到超过距离，或者所有的油箱都走遍了？
4、
learn && wrong;
1、有哪些需要是double的，最大油箱，距离，每公里油价，油价，距离都是double,不能用Int
2、距离为0处必须有加油站，不然无法触发
3、两个核心算法，
找到最低价的加油站，
判断是那种类型，采取不同策略，加满或者加一部分，下一个K低于当前，则加部分，下一个K不低于当前，则加满。
4、以及把目的当做加油站，单价为0，距离为D也挺厉害
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 510;
const int INF = 1000000000;
struct station {
double price, dis;//价格、与起点的距离
}st[maxn];
bool cmp(station a, station b) {
return a.dis < b.dis; //按距离从小到大排列
}
int main()
{
int n;
double Cmax, D, Davg;
scanf("%lf%lf%lf%d", &Cmax, &D, &Davg, &n);
for (int i = 0;i < n;++i) {
scanf("%lf%lf", &st[i].price, &st[i].dis);
}
st[n].price = 0; //数组后面放重点，价格为0 (!!!)
st[n].dis = D; //终点距离为D
sort(st, st + n, cmp); //将所有加油站按距离从小到大排序
if (st[0].dis != 0) {
printf("The maximum travel distance = 0.00\n");
}
else {
int now = 0; //当前所处加油站编号
double ans = 0, nowTank = 0, MAX = Cmax * Davg; //总花费，当前油量以及满油行驶距离
while (now < n) { //每次循环选出下一个需要到达的加油站
//选出从当前加油站满油能到大范围内的第一个油价低于当前油价的加油站
//如果没有低于当前油价的加油站，则选择价格最低那个
int k = -1; //最低油价的加油站的编号
double priceMIN = INF; //最低油价
for (int i = now + 1;i <= n && st[i].dis - st[now].dis <= MAX;++i) {
if (st[i].price < priceMIN) { //如果当前油价比最低油价低(其实就是找最低价格的加油
priceMIN = st[i].price;
k = i;
if (priceMIN < st[now].price) { //找到的最低加油站价格，比我的当前加油量还低，也就是结合了两个
break;
}
}
}
if (k == -1) break; //也就是没找到,满油状态下没找到，推出，输出结果
//下面为能找到可到达的加油站k，计算转移花费
//need为从Now到k需要的加油量
double need = (st[k].dis - st[now].dis) / Davg;
if (priceMIN < st[now].price) { //如果加油站k的油价低于当前油价，则加部分，只买足够到大K的加油量}
//只买足够到达加油站K的油
if (nowTank < need) {
ans += (need - nowTank) * st[now].price; //当前油量不足need;
nowTank = 0; //到达加油站k后油箱内油量为0
}
else {//当前油量超过need
nowTank -= need;
}
}
else { //如果加油站K的油价高于当前油价
ans += (Cmax - nowTank) * st[now].price; //将油箱加满
//到达加油站k后油箱内油量为Cmax - need
nowTank = Cmax - need;
}
now = k; //到达加油站，进入下层循环
}
if (now == n){ //能到达终点
printf("%.2f", ans);
}else {//不能到达终点
printf("The maximum travel distance = %.2f\n", st[now].dis + MAX);
}
}
return 0;
}
