To Fill or Not to Fill (25)

import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.TreeSet;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		double tank = in.nextInt();
		double totalTank = tank;
		double distance = in.nextDouble();
		double avg = in.nextDouble();
		int stations = in.nextInt();
		TreeSet<Station> set = new TreeSet<Station>();
		for(int i = 0;i<stations;i++){
			set.add(new Station(in.nextDouble(), in.nextInt()));
		}
		set.add(new Station(Double.MAX_VALUE,distance));
		Queue<Pair> queue = new PriorityQueue<Pair>();
		Iterator<Station> it = set.iterator();
		Station lastStation = it.next();
		queue.add(new Pair(lastStation.price, totalTank));
		double totalPrice = 0.0;
		double totalDistance = 0.0;
		double eps=1e-6;
		while(it.hasNext()){
			Station cur = it.next();//
			double needDis = cur.dis-lastStation.dis;//需要走的距离
			
			Iterator<Pair> pairIt = queue.iterator();//遍历油箱
			while(pairIt.hasNext()&&needDis>0){
				double needGas = needDis/avg;//需要的汽油
				Pair pair = pairIt.next();//
				double canRun = pair.gas*avg;//能走的距离
				if(canRun>=needDis){
					
					totalPrice += needGas*pair.price;//
					if(canRun==needDis){
						tank -= pair.gas+eps;//
						pair.gas = 0;//
					}else{
						tank -= needGas+eps;//总油箱减去花费的汽油
						pair.gas -= needGas;//
					}
					totalDistance += needDis;
					needDis=0;
					//走完 开始换油
					if(pair.price>=cur.price){
						queue.clear();
						queue.add(new Pair(cur.price, totalTank));
						tank = totalTank;//加满
					}else{
						//遍历pair找到比当前油价贵的 换掉
						while(pairIt.hasNext()){
							pair = pairIt.next();
							if(pair.price>=cur.price){
								tank -= pair.gas+eps;
								pairIt.remove();//
							}
						}
						if(tank<totalTank){
							queue.add(new Pair(cur.price, totalTank-tank+eps));//
							tank = totalTank;//加满
						}
					}
					break;
				}else{
					//当前的pair不能走到下一站
					totalPrice += pair.gas*pair.price;//
					tank -= pair.gas + eps;//
					needDis-=canRun;//需要走的距离减去可以走的距离
					totalDistance += canRun;
					pairIt.remove();//移除当前pair
				}
			}
			if(needDis>0){
				System.out.printf("The maximum travel distance = %.2f\n",totalDistance);
				return;
			}
			lastStation = cur;
		}
		System.out.printf("%.2f\n",totalPrice);

	}
	private static class Station implements Comparable<Station>{
		double price;
		double dis;
		public Station(double price, double dis) {
			this.price = price;
			this.dis = dis;
		}

		@Override
		public int compareTo(Station o) {
			if(this.dis>o.dis)
				return 1;
			else if(this.dis==o.dis)
				return (int)(this.price-o.price);
			return -1;
		}
	}
	private static class Pair implements Comparable<Pair>{
		double price;
		double gas;
		public Pair(double price, double gas) {
			this.price = price;
			this.gas = gas;
		}
		
		@Override
		public int compareTo(Pair o) {
			if(this.price>o.price)
				return 1;
			else if(this.price==o.price)
				return 0;
			return -1;
		}
	}
}

#include <iostream>
#include <algorithm>
using namespace std;
struct station{
    double price,dis;                //每个加油站的价格与起点距离
}s[510];
bool cmp(station a,station b){
    return a.dis<b.dis;             //将加油站按距离从小到大排序
}
const long long MIN=100000000;

int main(){
    int n;double cmax,distance,davg;  //除了加油站个数外其他数据都可能不是整数，用浮点型
    cin>>cmax>>distance>>davg>>n;
    for(int i=0;i<n;i++)
        cin>>s[i].price>>s[i].dis;
    sort(s,s+n,cmp);
    s[n].price=0;
    s[n].dis=distance;  //设置一个终点站

    if(s[0].dis!=0) printf("The maximum travel distance = 0.00\n");  //起点没有加油站，无法出发
    else{
        int now=0;
        double max=cmax*davg,sum=0,nowc=0;  //now为当前加油站编号，max为一箱油能跑多远，sum为累积油钱，nowc为当前油箱油量
        while(now<n){
            int k=-1;double minprice=MIN;   //k为最低油价的加油站编号
            for(int i=now+1;i<=n&&s[i].dis-s[now].dis<=max;i++){  //选择从当前加油站出发能到达的范围内第一个低于当前油价的加油站，没有的话就选范围内最低的一个
                if(s[i].price<minprice){
                    minprice=s[i].price;
                    k=i;
                    if(minprice<s[now].price) break;  //找到第一个低于当前油价的加油站，直接退出循环
                }
            }
            if(k==-1) break;  //范围内没有加油站
            double need=(s[k].dis-s[now].dis)/davg;  //need为从当前出发到达目标加油站所需油量
            if(minprice<s[now].price){    //若目标加油站油钱低于当前加油站
                if(need>nowc){            //若当前油量不够直接跑到目标加油站
                    sum+=(need-nowc)*s[now].price;
                    nowc=0;                        //加到可到目标加油站的油量，到达后油箱刚好用完
                }
                else
                    nowc-=need;                   //若当前油量超过所需油量，不加油直接跑到下个加油站
            }
            else{
                sum+=(cmax-nowc)*s[now].price;    //若目标加油站油价高于当前加油站，则在当前油站先加满油更划算
                nowc=cmax-need;
            }
            now=k;  //到达目标油站，更新当前油站编号
        }
        if(now==n) printf("%.2f\n",sum);  //能到终点，输出总油钱
        else printf("The maximum travel distance = %.2f\n",s[now].dis+max);  //不能到达终点，输出最远距离
    }
    return 0;
}
        

//贪心：先按照加油站距离升序排序，然后采取如下贪心策略：
    /*从当前所在加油站向后找（装满油能达到的范围内找），
         *如果有花费更少的的加油站x1，则加油加到能到达x1为止；
         *如果范围内的加油站花费都大，则加满油。
         *途中更新剩余油量，以及到达距离。
         *注意精度问题，剩余油量小于0不一定是无法到达，
         *因为精度的原因，在一定范围内，可以允许油量小于0（我设置的允许范围是10^(-10)）.
    */
#include <bits/stdc++.h>
#define inf 1e-10  // 允许的误差范围
using namespace std;
const int AX = 5e2 + 66 ;
struct Node {
	double p , d ;
	bool operator < ( const Node & x )const {
		return d < x.d ;
	}
} a[AX];
int main() {
	double V , d , x; int n ;
	scanf("%lf%lf%lf%d",&V,&d,&x,&n);
	for( int i = 0 ; i < n ; i++ ) {
		scanf("%lf%lf",&a[i].p,&a[i].d);
	}
	a[n++].d = d ;
	double res = 0.0 , dis = 0.0 , left = 0.0 ;
	sort( a , a + n );
	int f = 0 ;
	for( int i = 0 ; i < n ; i++ ) { 
		if( i ) f = 1 ; //走过距离是否为0
		int id = i ;
		left -= ( a[i].d - ( ( !i ) ? 0.0 : a[i-1].d ) ) / x ;
		if( a[i].d == d ) { dis = d ; break ; }
		if( left < 0 ) {
			if( 0-left > inf ) { 
				dis = ( ( !i ) ? 0.0 : a[i-1].d ) ; //超过允许的范围，则不可达
				break ;
			} else left = 0 ; //油量用光
		} else dis = a[i].d;
		for( int j = i + 1 ; j < n ; j++ ) {
			if( a[j].d > d ) break ;
			if( V * x >= a[j].d - a[i].d ) {  //可达范围内寻找花费比自己少的加油站
				if( a[j].p < a[i].p ) {
					id = j ;
					break ;
				}
			} else break ;
			id = j ;
		}
		if( a[id].p < a[i].p ) { //花费少更新油量为能达到此加油站
			double ned = ( a[id].d - a[i].d ) / x ;
			if( ned > left ) {
				res += ( ned - left ) * a[i].p ;
				left = ned ;
			}
		} else {  //范围内没有花费更少的则加满油
			res += ( V - left ) * a[i].p ;
			left = V ;
		}
	}
	if( dis < d ) {
		if( f ) printf("The maximum travel distance = %.2lf",dis+V*x);
		else printf("The maximum travel distance = 0.00");
	} else {
		printf("%.2lf",res);
	}
	return 0 ;
}

package go.jacob.day1129;

import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

/*
 * 处在当前加油站（起点加油站）的情况下
 * 情况1：600米范围内，有目的地——计算恰好能到目的地的油量                            
 * 情况2：600米范围内没有加油站，无论油价多贵——加满——能跑多远算多远                                                
 * 情况3：600米范围内有加油站：                                                                         
 * a:有比当前加油站的油价更便宜的加油站——加到恰好能到那个最近的油站的油量        
 * （注：1、如果有多个便宜的，还是要先选取最近的那个，而不是最便宜的那个；2、可能还有油剩余）
 * b:没有比当前加油站的油价更便宜的加油站——加满，然后在600范围内找到最便宜的加油站加油 
 */

/**
 * 参考解法：https://www.cnblogs.com/XBWer/p/3866486.html  * 
 * @author Administrator 贪心算法求解
 */
public class Demo2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double tank = sc.nextDouble(), distance = sc.nextDouble(), avgDist = sc.nextDouble();
        int n = sc.nextInt();
        List<Station> list = new ArrayList<Station>();
        for (int i = 0; i < n; i++) {
            Station s = new Station(sc.nextDouble(), sc.nextInt());
            list.add(s);
        }
        sc.close();
        Collections.sort(list);
        // 特殊情况：1.目的地址为原点；2.原点没有加油站
        if (distance == 0) {
            System.out.println("0.00");
            return;
        }
        if (list.get(0).getDist() != 0) {
            System.out.println("The maximum travel distance = 0.00");
            return;
        }
        int curStNum = 0;// 当前所处加油站编号
        double curGas = 0;// 当前的油量
        double curCost = 0;// 当前花费
        boolean flag = false;// 是否可以到达目的地
        double maxDis = tank * avgDist;
        while (!flag) {
            boolean tag = false;// 最大距离内是否有加油站
            boolean ifCheaper = false;// 是否有便宜的
            double cheapestPrice = 10000;// 找出最便宜的
            int cheapestNum = 0;// 没有更便宜的情况下，找出最便宜的
            for (int i = curStNum + 1; i < n; i++) {
                // 在可达范围内有加油站
                if ((list.get(i).getDist() - list.get(curStNum).getDist()) <= maxDis) {
                    tag = true;// 有加油站
                    if (list.get(i).getPrice() < list.get(curStNum).getPrice()) {// 情况3-a:在可达范围内有比当前更便宜的加油站
                        ifCheaper = true;
                        double dist = list.get(i).getDist() - list.get(curStNum).getDist();
                        double needGas = dist / avgDist - curGas;
                        curGas = 0;
                        curCost += needGas * list.get(curStNum).getPrice();
                        curStNum = i;
                        break;
                    }
                }
                if (list.get(i).getPrice() < cheapestPrice) {
                    cheapestPrice = list.get(i).getPrice();
                    cheapestNum = i;
                } else// 范围内没有加油站
                    break;
            }
            // 说明已经可以到达目的地了,情况1
            if (!ifCheaper && (distance - list.get(curStNum).getDist() <= maxDis)) {
                double dist = distance - list.get(curStNum).getDist();
                double needGas = dist / avgDist - curGas;
                curCost += needGas * list.get(curStNum).getPrice();
                System.out.printf("%.2f", curCost);
                return;
            }
            if (tag && !ifCheaper) {// 情况3-b：没有比当前加油站的油价更便宜的加油站——加满，然后在600范围内找到最便宜的加油站加油
                double needGas = tank - curGas;
                curCost += (needGas * list.get(curStNum).getPrice());
                double dist = list.get(cheapestNum).getDist() - list.get(curStNum).getDist();
                curGas = tank - dist / avgDist;
                curStNum = cheapestNum;
            } else if (!tag) {
                System.out.print("The maximum travel distance = ");
                System.out.printf("%.2f", list.get(curStNum).getDist() + maxDis);
                return;
            }
        }
    }

    /*
     * 加油站类
     */
    static class Station implements Comparable<Station> {
        private double price;
        private double dist;

        public Station(double price, double dist) {
            super();
            this.price = price;
            this.dist = dist;
        }

        @Override
        public int compareTo(Station s1) {
            return this.dist - s1.getDist() < 0 ? -1 : 1;
        }

        public double getPrice() {
            return price;
        }

        public double getDist() {
            return dist;
        }

    }
}

	

a = list(map(int,input().split()))
b = sorted([list(map(eval,input().split())) for i in range(a[3])],\
           key = lambda x: x[1]) + [[-1,a[1]],[float('inf'),0]]
if b[0][1] != 0:
    print('The maximum travel distance = 0.00')
    import sys;sys.exit(0)
i,m,n = 0,b[0] + [0],[]
while i < a[3]:
    j,q = i + 1,a[3] + 1
    while b[j][1] - m[1] <= a[0] * a[2]:
        if b[j][0] < m[0]:
            n.append([b[i][0],b[j][1] - sum(m[1:])])
            q = j
            break
        if b[j][0] < b[q][0]:
            q = j
        j += 1
    else:
        if b[q][1]:
            n.append([b[i][0],a[0] * a[2] - m[2]])
        else:
            print('The maximum travel distance = {:.2f}'.\
                  format(m[1] + a[0] * a[2]))
            break
    i,m = q,b[q] + [sum(m[1:]) + n[-1][1] - b[q][1]]
else:
    print('{:.2f}'.format(sum([i[0] * i[1] for i in n]) / a[2]))

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

struct Station{
	int Dis;
	double Price;
};

inline bool cmp(Station A, Station B) { return A.Dis < B.Dis; }

Station station[500];
double Cmax, Davg;
int D, N, dis = 0;

double go(double tank, int idx) {
	static double count = 0;
	static double Max = Cmax * Davg;
	if (dis + tank * Davg >= D) {
		dis = D;
		return count;						//	走到了
	}
	double nowPrice = station[idx].Price;
	double lowPrice = nowPrice;
	int pos = idx, p = idx + 1;
	while (p < N) {
		if (Max > station[p].Dis - dis) {
			if (station[p].Price < lowPrice) {
				pos = p;
				lowPrice = station[pos].Price;
			}
		}
		else break;
		p++;
	}
	if (lowPrice == nowPrice) {
		if (Max + dis > D) {										//	可以到了，加到够走到
			int len = D - dis;
			double c = len / Davg;
			dis = D;
			return count + (c - tank)*nowPrice;
		}
		count += (Cmax - tank)*nowPrice;
		if (idx + 1 >= N || Max + dis < station[idx + 1].Dis) {		//	走不到了，加满走到哪是哪
			dis += Max;
			return count;
		}
		int len = station[idx + 1].Dis - dis;
		double c = len / Davg;
		dis = station[idx + 1].Dis;
		return go(Cmax - c, idx + 1);								//	加满，走到下一站
	}
	int len = station[pos].Dis - dis;
	double c = len / Davg;
	if (c <= tank) {
		dis = station[pos].Dis;
		return go(tank - c, pos);									//	不加油，走到最优站
	}
	for (int i = idx + 1;i < pos;i++) {								//	油不够到最优站
		if (station[i].Price < nowPrice) {
			int len = station[i].Dis - dis;
			dis = station[i].Dis;
			double c = len / Davg;
			if (c <= tank)return go(tank - c, i);					//	不加油，走到中间站加油
			count += (c - tank)*nowPrice;
			return go(0, i);										//	加油到中间站再加油
		}
	}
	dis = station[pos].Dis;
	count += (c - tank)*nowPrice;
	return go(0, pos);

}

int main(int argc, const char* argv[]) {
	ios::sync_with_stdio(false);
	cin >> Cmax >> D >> Davg >> N;
	for (int i = 0;i < N;i++) cin >> station[i].Price >> station[i].Dis;
	sort(station, station + N, cmp);
	while (station[N - 1].Dis >= D)N--;
	if (station[0].Dis) {
		cout << "The maximum travel distance = 0.00";
		//system("pause");
		return 0;
	}
	double count = go(0, 0);
	if (dis - D)printf("The maximum travel distance = %.2f", (float)dis);
	else printf("%.2f", count);

	//system("pause");
	return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

struct station
{
	double distance;
	double price;

	bool operator<(const station &t)const {
		return distance < t.distance;
	}
};

station tem[505];

int main()
{
	double tank, distance, oil;
	int num;
	double price = 0, maxdistance = 0,max = 0;
	cin >> tank >> distance >> oil >> num;
	max = oil * tank;
	if (tank == 0 || oil == 0)
		return -1;
	for (int i = 0; i < num; i++)
	{
		scanf("%lf %lf", &tem[i].price, &tem[i].distance);
	}

	sort(tem, tem + num);
	tem[num].distance = distance;
	tem[num].price = 0;
//pat1033中有个case需要加此判断
	if (tem[0].distance != 0) {
		cout << "The maximum travel distance = 0.00\n";
		return 0;
	}
	double currentdistance = 0;
	double currentprice = tem[0].price;
	double left = 0;
	double totalprice = 0;

	int smallest = 0;
	int start = 0;

	for (int i = 0; i <= num; i++) {
		if (currentdistance + max < tem[i].distance) {
			if (start == 0) {
				break;
			}
			totalprice += (tank - left) * currentprice;
			left = (tank - (tem[smallest].distance - currentdistance) / oil);
			currentdistance = tem[smallest].distance;
			currentprice = tem[smallest].price;

			i = smallest;
			
			start = 0;
			continue;
		}

		if (tem[i].price <= currentprice) {
			totalprice += ((tem[i].distance - currentdistance) / oil - left) * currentprice;
			currentdistance = tem[i].distance;
			currentprice = tem[i].price;
			if (currentdistance == distance) {
				break;
			}
			left = 0;
			start = 0;
		}
		else {
			if (tem[i].price < tem[smallest].price || start == 0) {
				start = 1;
				smallest = i;
			}
		}
	}

	cout.setf(ios::fixed);
	cout.precision(2);
	if (currentdistance == distance) {
		cout << totalprice;
	}
	else {
		cout << "The maximum travel distance = " << currentdistance + max;
		if (currentdistance + max == distance)
			return -1;
	}

	return 0;
}

#include<iostream>
#include<algorithm>

using namespace std;

struct Station{
    double Pi;
    double Di;
};

bool Compare(Station a, Station b){
    if(a.Di==b.Di) return a.Pi<b.Pi;
    else return a.Di < b.Di;
}

int find(double Cmax){
    double D, Davg;
    int N;
    Station station[510];
    
    cin>>D>>Davg>>N;
    for(int i=0;i<N;i++) cin>>station[i].Pi>>station[i].Di;
    sort(station, station+N, Compare);
    
    double Position = 0, Price = 0, nowPrice = station[0].Pi, remainC = 0;
    int nowIndex = 0;

    while(Position < D){
        if(nowIndex==N-1){//后面没有加油站了，不找
            if(Position+Cmax*Davg>=D){
                Price+=((D-Position)/Davg-remainC)*nowPrice;
                printf("%.2f\n",Price);
            }else{
                printf("The maximum travel distance = %.2f\n", Position+Cmax*Davg);
            }
            return 0;
        }
        //后面至少还有一个加油站，找最便宜的或者第一个更便宜的
        int i = nowIndex+1;
        double minPi = 100000000, minDi = 0;
        int minIndex = 0;
        while(i<N && station[i].Di-Position<=Cmax*Davg){
            if(station[i].Pi <= nowPrice){//找到第一个小的
                minPi = station[i].Pi;
                minDi = station[i].Di;
                minIndex = i;
                break;
            }else{//找到所有范围内最小的
                if(station[i].Pi < minPi){
                    minPi = station[i].Pi;
                    minDi = station[i].Di;
                    minIndex = i;
                }
                i++;
            }
        }
        if(station[nowIndex+1].Di - Position > Cmax * Davg){//找不到，也就是去不了
            printf("The maximum travel distance = %.2f\n", Position+Cmax*Davg);
            return 0;
        }
        //找到小的直接去点
        if(minPi <= nowPrice){
            Price+=((minDi - Position)/Davg - remainC)* nowPrice;
            remainC = 0;
            Position = minDi;
            nowPrice = minPi;
            nowIndex = minIndex;
        }else{//找到大的看能不能直接去终点。
            if(Cmax*Davg>D-Position){//能去终点直接去
                Price += ((D-Position)/Davg - remainC)*nowPrice;
                printf("%.2f\n",Price);
                return 0;
            }else{//不能去终点去下个点
                Price += (Cmax - remainC)*nowPrice;
                remainC = Cmax - (minDi - Position) / Davg;
                Position = minDi;
                nowPrice = minPi;
                nowIndex = minIndex;
            }
        }
        
    }
}

int main(){
    double Cmax;
    while(cin>>Cmax){
        find(Cmax);
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define eps 1e-8
const int N=501;
/*
贪心
关键在于如何选择下一个汽油站
设加满油的情况下 能跑的最大距离为maxd (maxd=capacity*avg)
那么如果在当前位置的最大距离内 没有其他加油站
那肯定走不动了 GG

否则，从这些可达的加油站里，挑选第一个油价比自己低的
这样就能最快的用到比较低价的油
如果可达的汽油站 油价都比自己高 那肯定在当前位置我要把油加满
然后跑到这些新汽油站里燃油价格最低的那个

特判就是如果自己是可达位置里价格最低的加油站(最后一个加油站)
那直接到终点

所以在过程中我们维护花费的钱res 当前位置i 到达位置i之后的燃油数量cur

注意如果燃油价格相等 那我们肯定贪心的选择更远的加油站

*/
struct node{
	double p,d;
}a[N];
bool cmp(node A,node B){
	return A.d<B.d;
}
int main()
{
	int n;
	double capacity,D,avg;
	cin>>capacity>>D>>avg>>n;
	for(int i=0;i<n;i++){
		cin>>a[i].p>>a[i].d;
	}
	sort(a,a+n,cmp);
	a[n].d=D;
	double maxd=avg*capacity;
	for(int i=1;i<=n;i++){
		if(a[i].d-a[i-1].d > maxd){
			printf("The maximum travel distance = %.2f\n",a[i-1].d+maxd);
			return 0;
		}
	}

	double res=0,cur=0;
	int i=0;
	while(i<n){
		//printf("cur pos is %d cur gas is %.2f  cur res is %.2f\n",i,cur,res);
		double mp=1e18;
		int pos=-1;
		for(int j=i+1;j<n;j++){
			if(a[j].d - a[i].d >maxd) break;//距离太远
			if(mp > a[j].p || fabs(a[j].p - mp )<eps){//燃油价格相等的话 也应该跑过去
				mp=a[j].p;
				pos=j;
				if(mp < a[i].p || fabs(mp-a[i].p)<eps) break;
			}
		}
		if(mp > a[i].p || fabs(mp-a[i].p)<eps){//如果可达距离内的新汽油站 燃油价格比自己高
			if(a[i].d+maxd>=D){//直接跑到终点是否可行
				res+=((D-a[i].d)/avg-cur)*a[i].p;
				break;
			}
            res+=(capacity-cur)*a[i].p;
            cur=capacity-(a[pos].d-a[i].d)/avg;
		}
		else{//跑到价格更低的新汽油站
			if(cur*avg < a[pos].d-a[i].d){//当前燃油够不够
				res+=a[i].p*((a[pos].d - a[i].d - cur*avg)/avg);
				cur=0;
			}
			else{
				cur-=(a[pos].d-a[i].d)/avg;
			}
		}
		i=pos;//更新位置
	}
	printf("%.2f\n",res);
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
struct node {     double price;     double dis;     bool operator < (const node &rhs) const {         return dis < rhs.dis;     }
}station[maxn];
int main() {     std::ios::sync_with_stdio(false);     double C, D, P;     int N;     cin >> C >> D >> P >> N;     for (int i = 1; i <= N; ++i) {         cin >> station[i].price >> station[i].dis;     }     sort(station + 1, station + 1 + N);     if (station[1].dis != 0) {         printf("The maximum travel distance = %.2lf\n", 0);                 return 0;     }     station[N + 1].dis = D;     double mxdis = P * C;     int spos = 1;     double gas = 0;     double cost = 0;     bool flag = false;     while (spos <= N) {         if (station[spos].dis + mxdis < station[spos + 1].dis) {             flag = true;             break;         }         int nxp = spos;         for (int i = spos + 1; station[spos].dis + mxdis >= station[i].dis && i <= N + 1; ++i) {             if (station[i].price <= station[nxp].price) {                 nxp = i;                 break;             }         }         if (nxp == spos) {             cost += (C*1.0 - gas)*station[spos].price;             gas = C - (station[spos+1].dis-station[spos].dis)*1.0/P;             spos++;         }         else {             double dx = station[nxp].dis - station[spos].dis;             if (gas*P < dx) {                 double dp = dx / P - gas;                 cost += dp * station[spos].price;                 gas = 0;             }             else {                 gas -= dx / P;             }             spos = nxp;         }     }     if (flag) {         printf("The maximum travel distance = %.2lf\n", (station[spos].dis + mxdis)*1.0);     }     else {         printf("%.2lf\n", cost);     }     return 0;
}

	

cmax,d,davg,n = map(int,input().split())
lst1 = []
dis = cmax*davg
for i in range(n):
    tem = input().split()
    lst1.append([float(tem[0]),int(tem[1])])
lst1.sort(key = lambda x:(x[1],x[0]))
k = lst1[0][1]
lst = [lst1[0]]
for i in lst1:
    if k!=i[1]:
        lst.append(i)
        k = i[1]
lst.sort(key = lambda x:(x[1],x[0]))
i,j,price,travel,boo,cleft = 0,1,0.0,0,True,0
while j<len(lst) and i<len(lst)-1 and d>0:
    mi,boo1,tem1 = lst[i][0],False,[]  
    if lst[j][1]-lst[i][1]>dis:
            print("The maximum travel distance = "+str("%.2f"%(travel+dis)))
            boo= False
            break
    while j<len(lst) and i<len(lst)-1 and lst[j][1]-lst[i][1]<=dis:
         if lst[j][0]<mi:
            mi = lst[j][0]
            boo1 = True
            te = lst[j]
            break
         temp = list([j]+lst[j])
         tem1.append(temp) 
         j+=1
    if boo1:
        if cleft<=te[1]-lst[i][1]:
            price += lst[i][0]*(te[1]-lst[i][1]-cleft)/dis*cmax
            cleft = 0
        else:
            cleft -=te[1]-lst[i][1]       
        travel+=(te[1]-lst[i][1])
        d-=(te[1]-lst[i][1])
        if j<len(lst):
            i = int(j)
        else:
            break
        j = i+1
        if j==len(lst):
            break
        if lst[j][1]-lst[i][1]>dis:
            print("The maximum travel distance = "+str("%.2f"%(travel+dis)))
            boo= False
            break
    else:
        if d>dis:
            tem1.sort(key=lambda x:(x[1]))
            price += lst[i][0]*(dis-cleft)/dis*cmax       
            travel+=(tem1[0][2]-lst[i][1])
            cleft = dis - (tem1[0][2]-lst[i][1])
            d-=(tem1[0][2]-lst[i][1])
            i = int(tem1[0][0])
            j = i+1
        else:
            price+=lst[i][0]*(d-cleft)/dis*cmax
            travel+=d
            d-=(lst[j-1][1]-lst[i][1])
            cleft = d
            i = int(j-1)
            j=i+1
        
if boo:
    price = price+(d-cleft)/dis*cmax*lst[i][0]
    print("%.2f"%price)    

C,D,Dvg,N=map(int,input().split())
L=[list(map(float,input().split())) for _ in range(N)]
L.append([0,D])
L.sort(key=lambda x:x[1])
filter(lambda x:x[1]>D,L)
def tryDrive(s,gas,res):
    if s==len(L)-1:
        print('{:.2f}'.format(res))
        return
    right=min(D,L[s][1]+C*Dvg)
    r=max(i if L[i][1]<=right else s for i in range(s+1,len(L)))
    best=s
    for i in range(s+1,r+1):
        if L[i][0]<=L[s][0]:
            best=i
            break
    if r==s:
        d=L[s][1]+C*Dvg
        print('The maximum travel distance = {:.2f}'.format(d))
    elif best==s:
        tmp,sec=min((L[i][0],i) for i in range(s+1,r+1))
        cost=(L[sec][1]-L[s][1])/Dvg
        res+=(C-gas)*L[s][0]
        gas=C-cost
        return tryDrive(sec,gas,res)
    else:
        cost=(L[best][1]-L[s][1])/Dvg
        res+=(cost-gas)*L[s][0]
        gas=0
        return tryDrive(best,gas,res)
res=tryDrive(0,0,0)

#include <bits/stdc++.h>
#include <iostream>

using namespace  std;

struct position
{
    double price;
    double distance;
    position()=default;
    position(double p,double dis):price(p),distance(dis) {}
};

bool cmp(position &p1,position &p2){
    return p1.distance<p2.distance;
}

int main(){
    int n;
    double capacity,dis,use;
    scanf("%lf%lf%lf%d",&capacity,&dis,&use,&n);
    vector<position> data;
    for(int i=0;i<n;i++){
        double tmp1,tmp2;
        scanf("%lf%lf",&tmp1,&tmp2);
        data.push_back(position(tmp1,tmp2));
    }
    sort(data.begin(),data.end(),cmp);
    if(data[0].distance>0) {
        printf("The maximum travel distance = %.2lf",0.00);
        return 0;
    }
    double sum=0,cap=0;
    int i=0;
    bool out=false;
    double maxdis=0;
    while(i<n){
        maxdis=data[i].distance+use*capacity;
        int j=i+1;
        int minIndex=i+1;
        while(j<n){
            if(data[j].distance>maxdis) break;
            if(data[j].price<data[i].price) break;
            if(data[minIndex].price>data[j].price)
                minIndex=j;
            j++;
        }
        if(i==n-1){
            if(maxdis>=dis){
                sum+=((dis-data[i].distance)*1.0/use-cap)*data[i].price;
                out=true;
                break;
            }
            else{
                break;
            }
        }
        else if(j>=n){
            if(maxdis>=dis){
                double err=(dis-data[i].distance)*1.0/use;
                sum+=(err-cap)*data[i].price;
                out=true;
                break;
            }
            else{
                double err=(data[minIndex].distance-data[i].distance)*1.0/use;
                sum+=(capacity-cap)*data[i].price;
                cap=capacity-err;
                i=minIndex;
            }
        }
        else if(data[j].distance>maxdis&&j==i+1){
            break;
        }
        else if(data[j].distance<=maxdis&&data[j].price<data[i].price){
            double err=(data[j].distance-data[i].distance)*1.0/use;
            sum+=(err-cap)*data[i].price;
            cap=0;
            i=j;
        }
        else{
            double err=(data[minIndex].distance-data[i].distance)*1.0/use;
            sum+=(capacity-cap)*data[i].price;
            cap=capacity-err;
            i=minIndex;
        }
    }
    if(out==false)
        printf("The maximum travel distance = %.2lf",maxdis);
    else
        printf("%.2lf",sum);
    system("pause");
    return 0;
}