#include <bits/stdc++.h>
#include "nile.h"
using namespace std;
const long long INF=2e18;
struct Matrix
{
long long mat[3][3];
Matrix()
{
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
mat[i][j]=-INF;
}
}
}
};
inline Matrix multiply(const Matrix& a, const Matrix& b)
{
Matrix c;
for(int i=0; i<3; i++)
{
for(int k=0; k<3; k++)
{
if(a.mat[i][k]<=-INF/2)
{
continue;
}
for(int j=0; j<3; j++)
{
if(b.mat[k][j]<=-INF/2)
{
continue;
}
long long val=a.mat[i][k]+b.mat[k][j];
if(val>c.mat[i][j])
{
c.mat[i][j]=val;
}
}
}
}
return c;
}
struct Artifact
{
int w,a,b;
long long s;
};
struct Event
{
int d;
int idx;
int type;
bool operator<(const Event& other) const
{
return d<other.d;
}
};
struct Query
{
int d;
int id;
bool operator<(const Query& other) const
{
return d<other.d;
}
};
struct Seg
{
int n;
vector<Matrix> tree;
vector<long long> c1,c2;
Seg(int p) : n(p)
{
tree.resize(4*n+1);
c1.assign(n+1,-INF);
c2.assign(n+1,-INF);
if(n>=2)
{
build(1,2,n);
}
}
void um(int i, Matrix& m)
{
for(int r=0; r<3; r++)
{
for(int c=0; c<3; c++)
{
m.mat[r][c]=-INF;
}
}
m.mat[0][0]=0;
m.mat[0][1]=c1[i];
m.mat[0][2]=c2[i];
m.mat[1][0]=0;
m.mat[2][1]=0;
}
void build(int node, int start, int end)
{
if(start==end)
{
um(start,tree[node]);
return;
}
int mid=(start+end)/2;
build(2*node,start,mid);
build(2*node+1,mid+1,end);
tree[node]=multiply(tree[2*node+1],tree[2*node]);
}
void update(int node, int start, int end, int idx)
{
if(start==end)
{
um(start,tree[node]);
return;
}
int mid=(start+end)/2;
if(idx<=mid)
{
update(2*node,start,mid,idx);
}
else
{
update(2*node+1,mid+1,end,idx);
}
tree[node]=multiply(tree[2*node+1],tree[2*node]);
}
};
vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e)
{
int n=w.size();
int q=e.size();
vector<Artifact> arts(n);
long long total=0;
for(int i=0; i<n; i++)
{
arts[i]={w[i],a[i],b[i],(long long)a[i]-b[i]};
total+=a[i];
}
sort(arts.begin(),arts.end(), [](const Artifact& x, const Artifact& y)
{
return x.w<y.w;
});
if(n<2)
{
return vector<long long>(q,total);
}
vector<long long> s(n);
for(int i=0; i<n; i++)
{
s[i]=arts[i].s;
}
vector<Event> events;
for(int i=2; i<=n; i++)
{
events.push_back({arts[i-1].w-arts[i-2].w,i,1});
if(i>=3)
{
events.push_back({arts[i-1].w-arts[i-3].w,i,2});
}
}
sort(events.begin(),events.end());
vector<Query> qrs(q);
for(int i=0; i<q; i++)
{
qrs[i]={e[i],i};
}
sort(qrs.begin(),qrs.end());
Seg st(n);
vector<long long> results(q);
int ptr=0;
for(int i=0; i<q; i++)
{
while(ptr<(int)events.size() && events[ptr].d<=qrs[i].d)
{
int idx=events[ptr].idx;
if(events[ptr].type==1)
{
st.c1[idx]=s[idx-2]+s[idx-1];
}
else
{
st.c2[idx]=s[idx-3]+s[idx-1];
}
st.update(1,2,n,idx);
ptr++;
}
Matrix root=st.tree[1];
long long gain=max(root.mat[0][0],root.mat[0][1]);
results[qrs[i].id]=total-max(0LL,gain);
}
return results;
}
