#include "squirrel.h"
#include<bits/stdc++.h>
#define reg register
#define int long long
inline int min(reg int x,reg int y){return x<y?x:y;}
inline bool cmin(reg int &x,reg int y){return x>y?x=y,1:0;}
inline bool cmax(reg int &x,reg int y){return x<y?x=y,1:0;}
const int N=5e5+10;
int n,mn[N<<2],tag[N<<2],st[20][N],w[N];
inline void brush(reg int o,reg int k){mn[o]+=k,tag[o]+=k;}
inline void pushdown(reg int o){if (tag[o]) brush(o<<1,tag[o]),brush(o<<1|1,tag[o]),tag[o]=0;}
inline void pushup(reg int o){mn[o]=min(mn[o<<1],mn[o<<1|1]);}
void modify(reg int o,reg int l,reg int r,reg int L,reg int R,reg int k){
    if (L<=l&&r<=R) return brush(o,k); reg int mid=l+r>>1; pushdown(o);
    if (L<=mid) modify(o<<1,l,mid,L,R,k); if (R>mid) modify(o<<1|1,mid+1,r,L,R,k); pushup(o);
}
int find(reg int o,reg int l,reg int r,reg int x){
    if (mn[o]>0) return l-1; if (l==r) return l; pushdown(o);
    reg int mid=l+r>>1,t=x>mid?find(o<<1|1,mid+1,r,x):mid;
    return t==mid?find(o<<1,l,mid,x):t;
}
int query(reg int o,reg int l,reg int r,reg int L,reg int R){
    if (L<=l&&r<=R) return mn[o]; reg int mid=l+r>>1,res=1e18; pushdown(o);
    if (L<=mid) cmin(res,query(o<<1,l,mid,L,R)); if (R>mid) cmin(res,query(o<<1|1,mid+1,r,L,R));
    return res;
}
inline int chk(reg int x,reg int y){return w[x]<w[y]?x:y;}
inline int qry(reg int l,reg int r){reg int L=std::__lg(r-l+1); return chk(st[L][l],st[L][r-(1<<L)+1]);}
#undef int
long long fly(std::vector<int> D, std::vector<int> H, std::vector<int> W, int L, int R) {
    #define int long long
    n=D.size(); 
    for (reg int i=1;i<=n;i++) st[0][i]=i,w[i]=W[i-1];
    for (reg int j=1;1<<j<=n;j++) for (reg int i=1;i+(1<<j)-1<=n;i++) st[j][i]=chk(st[j-1][i],st[j-1][i+(1<<j-1)]);
    reg int ans=0; D.push_back(D.back()+R);
    modify(1,1,n,1,1,H[0]-L);
    for (reg int i=2,now=L;i<=n+1;i++){
        reg int d=D[i-1]-D[i-2];
        // std::cerr<<"<< "<<d<<" "<<now<<"\n";
       reg int qwq=0;
        while (now<d){
            ++qwq; assert(qwq<=4);
            // std::cerr<<"qwq\n";
            reg int L=find(1,1,n,i-1)+1;
            // std::cerr<<L<<" "<<i<<"\n";
            if (L==i) return -1;
            reg int nw=min(query(1,1,n,L,i-1),d-now);
            // std::cerr<<query(1,1,n,3,3)<<"\n";
            reg int id=qry(L,i-1); modify(1,1,n,id,i-1,-nw);
            ans+=w[id]*nw,now+=nw;
        }
        now-=d;
        // std::cerr<<now<<"\n";
        cmin(now,H[i-1]);
        if (i<=n) modify(1,1,n,i,i,H[i-1]-now);
    }    
    return ans;
}