#include "squirrel.h"
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < ll,ll >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
// #define int ll
// #define N 
using namespace std;
long long fly(std::vector<int> D, std::vector<int> H, std::vector<int> W, int L, int R)
{
    int n = D.size();
    deque<pa> g;
    g.push_back(mp(0ll,0ll));
    g.push_back(mp(L,0ll));
    if (H[0]!=L)
        g.push_back(mp(H[0],1ll*(H[0]-L)*W[0]));
    ll sm=0;
        // for (auto [u,v]:g) cout<<u-sm<<":"<<v<<",";
        // cout<<endl;
    for (int i=1;i<n;i++)
    {
        sm+=D[i]-D[i-1];
        while (g.size()&&g[0].fi<sm) 
        {
            pa nxt=mp(-1ll,-1ll);
            if (g.size()>1&&g[1].fi>sm) nxt=mp(sm,g[0].se+(g[1].se-g[0].se)/(g[1].fi-g[0].fi)*(sm-g[0].fi));
            g.pop_front();
            if (nxt.fi!=-1) g.push_front(nxt);
        }
        // cout<<"----";
        // for (auto [u,v]:g) cout<<u-sm<<":"<<v<<",";
        // cout<<endl;
        while (g.size()&&g[sz(g)-1].fi>sm+H[i]) 
        {
            pa nxt=mp(-1ll,-1ll);
            if (g.size()>1&&g[sz(g)-2].fi<sm+H[i]) 
                nxt=mp(sm+H[i],g[sz(g)-2].se+
                (g[sz(g)-1].se-g[sz(g)-2].se)/
                (g[sz(g)-1].fi-g[sz(g)-2].fi)*
                (sm+H[i]-g[sz(g)-2].fi));
            g.pop_back();
            if (nxt.fi!=-1) g.push_back(nxt);
        }
        if (g.empty()) return -1;
        while (g.size()>=2&&
        (g[sz(g)-1].se-g[sz(g)-2].se)
        /(g[sz(g)-1].fi-g[sz(g)-2].fi)>W[i]) g.pop_back();
        if (g.size()&&g.back().fi!=sm+H[i]) 
        {
            g.push_back(mp(sm+H[i],g.back().se+(sm+H[i]-g.back().fi)*W[i]));
        }
        // cout<<"!!"<<i<<endl;
    }
    while (g.size()&&g[sz(g)-1].fi>sm+R) 
    {
        if (g.size()<=1) return -1;
        pa nxt=mp(-1ll,-1ll);
        if (g.size()>1&&g[sz(g)-1].fi>sm+R&&g[sz(g)-2].fi<sm+R) 
            nxt=mp(sm+R,g[sz(g)-2].se+
                (g[sz(g)-1].se-g[sz(g)-2].se)/
                (g[sz(g)-1].fi-g[sz(g)-2].fi)*
                (sm+R-g[sz(g)-2].fi));
        g.pop_back();
        if (nxt.fi!=-1) g.push_back(nxt);
    }
    return g.back().se;
}