#include "nile.h"
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <utility>
#include <cmath>
#define fr first
#define sc second
using namespace std;
const long long MAX = 1e5+5;
const long long MOD = 998244353, P = 29;
const long long MIX = 1e15+7;
struct tree{
long long sz=1;
vector<long long> tre[2];
void full(long long o){
while(sz<o){
sz*=2;
}
tre[0].assign(sz*2-1,-MIX);
tre[1].assign(sz*2-1,-MIX);
}
void add(long long ps, long long v, long long z){
add(ps, v, z, 0, sz, 0);
}
void add(long long ps, long long v, long long z, long long lr, long long rl, long long x){
if(rl-lr==1){
tre[z][x]=v;
return;
}
long long mid=(rl+lr)/2;
if(mid<=ps){
add(ps, v, z, mid, rl, x*2+2);
}
else{
add(ps, v, z, lr, mid, x*2+1);
}
tre[z][x]=max(tre[z][x*2+1],tre[z][x*2+2]);
}
long long take(long long L, long long R, long long z){
return take(L, R, z, 0, sz-1, 0);
}
long long take(long long L, long long R, long long z, long long lr, long long rl, long long x){
if(L>rl || lr>R){
return -MIX;
}
if(L<=lr && rl<=R){
return tre[z][x];
}
long long mid=(rl+lr)/2;
return max(take(L, R, z, mid+(rl+lr)%2, rl, x*2+2), take(L, R, z, lr, mid, x*2+1));
}
};
std::vector<long long> calculate_costs(std::vector<long long> W, std::vector<long long> A, std::vector<long long> B, std::vector<long long> E) {
tree tr;
long long q = E.size();
long long n = W.size(),sum=0;
tr.full(n);
for(auto i : A){
sum+=i;
}
vector<pair<long long,long long>> ans;
vector<long long> R(q, 0),ms;
vector<pair<long long,long long>> vec;
for(long long i=0;i<n;i++){
vec.push_back({W[i],B[i]-A[i]});
if(i==0){
ms.push_back(vec[i].sc);
}
else{
ms.push_back(ms.back()+vec[i].sc);
}
}
sort(vec.begin(),vec.end());
vector<pair<long long,pair<long long,long long>>> color;
vector<long long> price(n,0);
for(long long i=0;i<n;i++) color.push_back({i,{i,i}});
set<pair<long long,pair<long long,long long>>> dif;
for(long long i=1;i<n;i++){
dif.insert({vec[i].fr-vec[i-1].fr,{i-1,1}});
}
for(long long i=1;i<n-1;i++){
dif.insert({vec[i+1].fr-vec[i-1].fr,{i,2}});
}
for(long long i=0;i<n;i+=2){
tr.add(i, vec[i].sc, 0);
}
for(long long i=1;i<n;i+=2){
tr.add(i, vec[i].sc, 1);
}
ans.push_back({-1,sum});
while(!dif.empty()){
pair<long long,pair<long long,long long>> pr=*dif.begin();
dif.erase(dif.begin());
if(pr.sc.sc==1){
long long clr1 = color[pr.sc.fr].fr, clr2 = color[pr.sc.fr + 1].fr;
if(color[clr1].sc.sc-color[clr1].sc.fr>color[clr2].sc.sc-color[clr2].sc.fr){
color[clr1].sc.sc=color[clr2].sc.sc;
for(long long i=color[clr2].sc.fr;i<=color[clr2].sc.sc;i++){
color[i].fr=clr1;
}
sum-=price[clr1]+price[clr2];
if((color[clr1].sc.sc-color[clr1].sc.fr)%2==0){
if(color[clr1].sc.fr==0){
price[clr1]=ms[color[clr1].sc.sc]-tr.take(color[clr1].sc.fr,color[clr1].sc.sc,color[clr1].sc.fr%2);
}
else{
price[clr1]=ms[color[clr1].sc.sc]-ms[color[clr1].sc.fr-1]-tr.take(color[clr1].sc.fr,color[clr1].sc.sc,color[clr1].sc.fr%2);
}
sum+=price[clr1];}
else{
if(color[clr1].sc.fr==0){
price[clr1]=ms[color[clr1].sc.sc];
}
else{
price[clr1]=ms[color[clr1].sc.sc]-ms[color[clr1].sc.fr-1];
}
sum+=price[clr1];
}
}
else{
color[clr2].sc.fr=color[clr1].sc.fr;
for(long long i=color[clr1].sc.fr;i<=color[clr1].sc.sc;i++){
color[i].fr=clr2;
}
sum-=price[clr1]+price[clr2];
if((color[clr2].sc.sc-color[clr2].sc.fr)%2==0){
if(color[clr2].sc.fr==0){
price[clr2]=ms[color[clr2].sc.sc]-tr.take(color[clr2].sc.fr,color[clr2].sc.sc,color[clr2].sc.fr%2);
}
else{
price[clr2]=ms[color[clr2].sc.sc]-ms[color[clr2].sc.fr-1]-tr.take(color[clr2].sc.fr,color[clr2].sc.sc,color[clr2].sc.fr%2);
}
sum+=price[clr2];
}
else{
if(color[clr2].sc.fr==0){
price[clr2]=ms[color[clr2].sc.sc];
}
else{
price[clr2]=ms[color[clr2].sc.sc]-ms[color[clr2].sc.fr-1];
}
sum+=price[clr2];
}
}
}
else{
tr.add(pr.sc.fr, vec[pr.sc.fr].sc, (pr.sc.fr+1)%2);
long long clr = color[pr.sc.fr].fr;
sum-=price[clr];
if((color[clr].sc.sc-color[clr].sc.fr)%2==0){
if(color[clr].sc.fr==0){
price[clr]=ms[color[clr].sc.sc]-tr.take(color[clr].sc.fr,color[clr].sc.sc,color[clr].sc.fr%2);
}
else{
price[clr]=ms[color[clr].sc.sc]-ms[color[clr].sc.fr-1]-tr.take(color[clr].sc.fr,color[clr].sc.sc,color[clr].sc.fr%2);
}
}
sum+=price[clr];
}
if(ans.back().fr==pr.fr){
ans.pop_back();
}
ans.push_back({pr.fr,sum});
}
for(long long i=0;i<ans.size();i++){
long long lr=0,rl=ans.size();
while(rl-lr!=1){
long long mid=(rl+lr)/2;
if(ans[mid].fr<=E[i]){
lr=mid;
}
else{
rl=mid;
}
}
R[i]=ans[lr].sc;
}
return R;
}
// signed main(){
// long long f,g;
// cin>>f>>g;
// vector<long long> w,a,b,e;
// for(long long i=0;i<f;i++){
// long long y;
// cin>>y;
// w.push_back(y);
// }
// for(long long i=0;i<f;i++){
// long long y;
// cin>>y;
// a.push_back(y);
// }
// for(long long i=0;i<f;i++){
// long long y;
// cin>>y;
// b.push_back(y);
// }
// for(long long i=0;i<g;i++){
// long long y;
// cin>>y;
// e.push_back(y);
// }
// vector<long long> ui=calculate_costs(w,a,b,e);
// for(auto i : ui){
// cout<<i<<endl;
// }
// }
