#include "nile.h"
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
    if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
    if(x > y) x = y;
}

inline int popcnt(int x){
    return __builtin_popcount(x);
}

inline int ctz(int x){
    return __builtin_ctz(x);
}


int n,m;
int val[100005],w[100005],ord[100005],tmp[100005];

bool cmp(int x,int y){
    return w[x] < w[y];
}
struct M{
    ll v[3][3];
    M(){
        memset(v,0xcf,sizeof(v));
    }
}tr[100005],tree[400005];
#define ls (rt * 2)
#define rs (rt * 2 + 1)
M operator *(M p,M q){
    M ans;
    rep(i,0,2){
        rep(j,0,2){
            ans.v[i][j] = -linf;
            rep(k,0,2) chkmax(ans.v[i][j],p.v[i][k] + q.v[k][j]);
        }
    }
    return ans;
}

void gtrans(int p,int lim){
    tr[p] = M();
    tr[p].v[0][0] = 0;
    tr[p].v[1][2] = 0;
    if(p >= 2 && w[p] - w[p - 1] <= lim) tr[p].v[1][0] = val[p];
    if(p >= 3 && w[p] - w[p - 2] <= lim) tr[p].v[2][0] = val[p];
    tr[p].v[0][1] = val[p];
}

void pushup(int rt){
    tree[rt] = tree[ls] * tree[rs];
}

void build(int rt,int l,int r){
    if(l == r){
        gtrans(l,-1);
        tree[rt] = tr[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(ls,l,mid);build(rs,mid+1,r);
    pushup(rt);
}

void modify(int rt,int l,int r,int pos){
    if(l == r){
        tree[rt] = tr[l];
        return;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid) modify(ls,l,mid,pos);
    else modify(rs,mid+1,r,pos);
    pushup(rt);
}

void mdf(int p,int lim){
    gtrans(p,lim);
    modify(1,1,n,p);
}

int sz;
pii P[200005],Q[100005];
vector<ll> calculate_costs(vector<int> W, vector<int> A,vector<int> B, vector<int> E){
    n = SZ(W);m = SZ(E);
    assert(SZ(A) == n && SZ(B) == n);
    ll bas = 0;
    rep(i,0,n - 1){
        bas += A[i];
        val[i + 1] = A[i] - B[i];
        w[i + 1] = W[i];
    }
    rep(i,1,n) ord[i] = i;
    sort(ord + 1,ord + n + 1,cmp);
    rep(i,1,n) tmp[i] = w[ord[i]];
    rep(i,1,n) w[i] = tmp[i];
    rep(i,1,n) tmp[i] = val[ord[i]];
    rep(i,1,n) val[i] = tmp[i]; 
    rep(i,1,n){
        if(i >= 2) P[++sz] = mkp(w[i] - w[i - 1],i);
        if(i >= 3) P[++sz] = mkp(w[i] - w[i - 2],i);
    }
    sort(P + 1,P + sz + 1);
    rep(i,0,m - 1) Q[i + 1] = mkp(E[i],i);
    sort(Q + 1,Q + m + 1);
    build(1,1,n);
    int j = 0;
    vector <ll> ans(m);
    rep(i,1,m){
        while(j < sz && P[j + 1].first <= Q[i].first){
            j++;
            mdf(P[j].second,P[j].first);
        }
        ans[Q[i].second] = bas - tree[1].v[0][0];
    }
    return ans;
}
/*
g++ grader.cpp nile.cpp -o grader.exe -Wall -Wshadow -O2 -std=c++14
*/