题目##
农夫约翰决定去做一个环游国家旅行，为了不让他的奶牛们感到孤单，于是他决定租一辆货车带领他的奶牛们一起去旅行。这辆货车的油箱最多可以承载G 个单位的油，同时为了简化问题，规定每一个单位的油可以行使一个单位的距离。约翰从起点出发到终点总共要经过D 个单位的距离。约翰知道自己很有可能要在中途的过程中加几次油。他将中途的N 个加油站（加油站看成是排成一条直线的）的位置都记录下来了。对于每一个加油站，他记录了这个加油站到起点的距离Xi，同时也记录了这个加油站的每个单位的油价Yi。
问题描述：
给定以上这些信息，约翰开始的时候有B 个单位的油，请帮助计算约翰为了
到达终点至少要在中途花费多少钱加油。如果约翰不能到达终点，那么就输出-1。
注意这题的结果可能超过longint 的范围。
输入格式：
第一个四个整数，N,G,B,D。
接下来N 行，每行两个整数，分别表示每个加油站的Xi 和Yi。
输出格式：
输出为了到达终点最少需要花费的钱的数量，如果不能到达就输出-1。
输入输出样例：
fuel.in
4 10 3 17
2 40
9 15
5 7
10 12
fuel.out
174
数据范围：
1<=G<=1000000,1<=D<=1000000000,1<=N<=50000,0<=Xi<=D,1<=Yi<=1000000，0<=B<=D。
样例说明：样例中，约翰先是行使了2 个单位的距离，然后在位置为2 的加油站购买了2 个单位的油，花费2*40=80，然后在位置为5 的加油站加满了油，花费7*10=70，然后他到达位置为10 的加油站，加了两个单位的油，花费为12*2，于是他总的花费是80+70+24=174。
引例##
看到这道题目，首先想到的是DP，但是1<=N<=50000，1<=D<=1000000000可以很容易地让我们放弃这个想法（光是内存方面就明显不允许）。然而，看到油价、路程等，我就联想到了之前做过的题目：Duff and Meat(CodeForces 588A)。这道题目大意是这样子的：Duff要在N天内购买食材，第i天的食物需求与单位食物价格分别是x[i]与p[i]，第i天不仅可以购买当天的食物，也可以把后面任意几天的食物都买下。当时看到这题我也是手足无措，是看到tips里的greedy（贪心）才想到了一个算法：在第i天时，只要后面的连续几天的食物价格大于当天食物价格，就在这一天都预先买下。这题的核心思路大致相仿。
题解##
根据上面的引例中的算法，我们可以写出一个朴素的算法，即先对数组x升序排序，这会使后面的算法操作方便许多。然后在按照上面的步骤进行贪心。对每一站进行遍历，找出后面比它更便宜的一站，时间复杂度为O(n^2)。在极限数据N=50000下很有可能超时。这时候就需要用到一点技巧，在贪心前花费O(N)的时间利用栈的特性进行预处理，这样，整个程序的时间复杂度就可以降低到O(N)，秒杀N=50000的情况。
参考程序##
var
ns,s,x,y:array[0..50001] of int64;
ans,sl,gasn,st,n,g,b,d,j,p:int64;
i:longint;
function min(a,b:int64):int64;
begin
if a>b then exit(b);
exit(a);
end;
procedure sort(l,r:longint);
var
i,j,x1,y1:int64;
begin
i:=l;j:=r;
x1:=x[(l+r) div 2];
repeat
while x[i]<x1 do inc(i);
while x1<x[j] do dec(j);
if not(i>j) then begin
y1:=x[i];x[i]:=x[j];x[j]:=y1;
y1:=y[i];y[i]:=y[j];y[j]:=y1;
inc(i);dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;
begin
assign(input,'fuel.in');assign(output,'fuel.out');
reset(input);rewrite(output);
readln(n,g,b,d);
for i:=1 to n do readln(x[i],y[i]);
sort(1,n);sl:=0;
for i:=n downto 1 do begin
while (sl>=1) and (y[s[sl-1]]>y[i]) do dec(sl);
if sl=0 then ns[i]:=-1 else ns[i]:=s[sl-1];
s[sl]:=i;inc(sl);
end;//栈优化
dec(b,x[1]);//把车开到第一站，自然需要花费x[1]单位的汽油
ans:=0;
for i:=1 to n do
if b<0 then begin//中途b<0时，必定开不到终点了
writeln(-1);
close(input);close(output);
halt;
end else begin
if ns[i]=-1 then gasn:=min(g,d-x[i]) else gasn:=min(g,x[ns[i]]-x[i]);
if gasn>b then begin//如果油有多的，则掏钱买
ans:=ans+(gasn-b)*y[i];
b:=gasn;
end;
if i=n then dec(b,d-x[i]) else dec(b,x[i+1]-x[i]);
end;
if b<0 then begin
writeln(-1);
close(input);close(output);
halt;
end else writeln(ans);
close(input);close(output);
end.