#include "nile.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct ura
{
long long a,b,w;
};
bool cmp(ura a, ura b)
{
return a.w<b.w;
}
ura vec[100005];
int n;
long long inf=1e16;
long long aint[400006][4][4];
long long d;
void merge(int node,int fiu1,int fiu2,int st,int dr,int mij)
{
for(int e1=0; e1<=2; e1++)
{
for(int e2=0; e2<=2; e2++)
{
aint[node][e1][e2]=aint[fiu1][e1][0]+aint[fiu2][0][e2];
if(vec[mij+1].w-vec[mij].w<=d)
aint[node][e1][e2]=min(aint[node][e1][e2],aint[fiu1][e1][1]+aint[fiu2][1][e2]);
if(vec[mij+2].w-vec[mij].w<=d)
aint[node][e1][e2]=min(aint[node][e1][e2],aint[fiu1][e1][1]+aint[fiu2][2][e2]);
if(vec[mij+1].w-vec[mij-1].w<=d)
aint[node][e1][e2]=min(aint[node][e1][e2],aint[fiu1][e1][2]+aint[fiu2][1][e2]);
}
}
}
void update(int node,int st,int dr,int poz)
{
if(st+1==dr)
{
aint[node][0][0]=vec[st].a+vec[dr].a;
aint[node][1][0]=vec[st].b+vec[dr].a;
aint[node][0][1]=vec[st].a+vec[dr].b;
aint[node][1][1]=vec[st].b+vec[dr].b;
aint[node][2][0]=vec[st].a+vec[dr].b;
aint[node][0][2]=vec[st].b+vec[dr].a;
aint[node][2][1]=inf;
aint[node][1][2]=inf;
aint[node][2][2]=inf;
if(vec[dr].w-vec[st].w<=d)
{
aint[node][0][0]=vec[st].b+vec[dr].b;
}
return;
}
else if(st+2==dr)
{
int mij=(st+dr)/2;
aint[node][0][0]=vec[st].a+vec[dr].a+vec[mij].a;
aint[node][2][2]=inf;
if(vec[dr].w-vec[mij].w<=d)
{
aint[node][1][0]=vec[st].b+vec[dr].b+vec[mij].b;
}
else
{
aint[node][1][0]=vec[st].b+vec[dr].a+vec[mij].a;
}
if(vec[mij].w-vec[st].w<=d)
{
aint[node][0][1]=vec[st].b+vec[dr].b+vec[mij].b;
}
else
{
aint[node][0][1]=vec[st].a+vec[dr].b+vec[mij].a;
}
aint[node][1][1]=vec[st].b+vec[dr].b+vec[mij].a;
aint[node][2][0]=vec[st].a+vec[mij].b+vec[dr].a;
aint[node][0][2]=vec[mij].b+vec[dr].a+vec[st].a;
aint[node][2][1]=vec[mij].b+vec[dr].b+vec[st].a;
aint[node][1][2]=vec[mij].b+vec[dr].a+vec[st].b;
if(vec[dr].w-vec[st].w<=d)
{
aint[node][0][0]=vec[st].b+vec[dr].b+vec[mij].a;
}
if(vec[dr].w-vec[mij].w<=d)
{
aint[node][0][0]=vec[st].a+vec[dr].b+vec[mij].b;
}
if(vec[mij].w-vec[st].w<=d)
{
aint[node][0][0]=vec[st].b+vec[dr].a+vec[mij].b;
}
return;
}
int mij=(st+dr)/2;
if(poz<=mij)
update(node*2,st,mij,poz);
if(poz>=mij+1)
update(node*2+1,mij+1,dr,poz);
merge(node,node*2,node*2+1,st,dr,mij);
}
void build(int node,int st,int dr)
{
if(st+1==dr)
{
aint[node][0][0]=vec[st].a+vec[dr].a;
aint[node][1][0]=vec[st].b+vec[dr].a;
aint[node][0][1]=vec[st].a+vec[dr].b;
aint[node][1][1]=vec[st].b+vec[dr].b;
aint[node][2][0]=vec[st].a+vec[dr].b;
aint[node][0][2]=vec[st].b+vec[dr].a;
aint[node][2][1]=inf;
aint[node][1][2]=inf;
aint[node][2][2]=inf;
if(vec[dr].w-vec[st].w<=d)
{
aint[node][0][0]=vec[st].b+vec[dr].b;
}
return;
}
else if(st+2==dr)
{
int mij=(st+dr)/2;
aint[node][0][0]=vec[st].a+vec[dr].a+vec[mij].a;
aint[node][2][2]=inf;
if(vec[dr].w-vec[mij].w<=d)
{
aint[node][1][0]=vec[st].b+vec[dr].b+vec[mij].b;
}
else
{
aint[node][1][0]=vec[st].b+vec[dr].a+vec[mij].a;
}
if(vec[mij].w-vec[st].w<=d)
{
aint[node][0][1]=vec[st].b+vec[dr].b+vec[mij].b;
}
else
{
aint[node][0][1]=vec[st].a+vec[dr].b+vec[mij].a;
}
aint[node][1][1]=vec[st].b+vec[dr].b+vec[mij].a;
aint[node][2][0]=vec[st].a+vec[mij].b+vec[dr].a;
aint[node][0][2]=vec[mij].b+vec[dr].a+vec[st].a;
aint[node][2][1]=vec[mij].b+vec[dr].b+vec[st].a;
aint[node][1][2]=vec[mij].b+vec[dr].a+vec[st].b;
if(vec[dr].w-vec[st].w<=d)
{
aint[node][0][0]=min(aint[node][0][0],vec[st].b+vec[dr].b+vec[mij].a);
}
if(vec[dr].w-vec[mij].w<=d)
{
aint[node][0][0]=min(aint[node][0][0],vec[st].a+vec[dr].b+vec[mij].b);
}
if(vec[mij].w-vec[st].w<=d)
{
aint[node][0][0]=min(aint[node][0][0],vec[st].b+vec[dr].a+vec[mij].b);
}
return;
}
int mij=(st+dr)/2;
build(node*2,st,mij);
build(node*2+1,mij+1,dr);
merge(node,node*2,node*2+1,st,dr,mij);
}
pair<int,int>qu[300005];
bool cmp1(pair<int,int> a,pair<int,int> b)
{
return a.second<b.second;
}
priority_queue<pair<int,int>>mincost;
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E)
{
int q = (int)E.size();
n = A.size();
for(int i=1; i<=n; i++)
{
vec[i].a=A[i-1];
vec[i].b=B[i-1];
vec[i].w=W[i-1];
}
sort(vec+1,vec+n+1,cmp);
for(int i=2; i<=n; i++)
{
if(i>=2)
{
mincost.push({vec[i].w-vec[i-1].w,i});
mincost.push({vec[i].w-vec[i-1].w,i-1});
}
if(i>=3)
{
mincost.push({vec[i].w-vec[i-2].w,i});
mincost.push({vec[i].w-vec[i-2].w,i-1});
mincost.push({vec[i].w-vec[i-2].w,i-2});
}
}
vector<long long>rasp(q);
for(int i=0; i<q; i++)
{
qu[i].first=i;
qu[i].second=E[i];
}
sort(qu,qu+q,cmp1);
d=1e9+9;
build(1,1,n);
for(int i=q-1; i>=0; i--)
{
d=qu[i].second;
while(mincost.size() && mincost.top().first>d)
{
update(1,1,n,mincost.top().second);
mincost.pop();
}
rasp[qu[i].first]=aint[1][0][0];
}
return rasp;
}
