#include <bits/stdc++.h>
#include <cstdlib>
#include <stdlib.h>
using namespace std;
#define ull unsigned long long
#define ld long double
#define ll long long
// #define int long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
int mod = 1e9 + 7;
const ll inf = 1e18;
const int N = 1e5 + 50, K = 22;
// #include "nile.h"
ll n;
ll sum = 0;
vector<ll> c;
vector<pii> q;
struct dsu{
vector<ll> sz, p, minodd, mineven, minidx;
ll resodd = 0, reseven = 0;
dsu(int n){
sz = p = minodd = mineven = minidx = vector<ll> (n + 5, 0ll);
for(int i = 0; i < n; i++)
sz[i] = 1, p[i] = i, minodd[i] = mineven[i] = c[i], minidx[i] = i, resodd += c[i], reseven += c[i];
}
ll find(ll u){
return p[u] == u ? u : p[u] = find(p[u]);
}
bool merge(int a, int b){
a = find(a);
b = find(b);
if(a == b)
return false;
if(sz[a] < sz[b])
swap(a, b);
p[b] = a;
resodd -= minodd[a];
resodd -= minodd[b];
reseven -= mineven[a];
reseven -= mineven[b];
minodd[a] = min(minodd[a], minodd[b]);
mineven[a] = min(mineven[a], mineven[b]);
minidx[a] = min(minidx[a], minidx[b]);
sz[a] += sz[b];
resodd += minodd[a];
reseven += mineven[a];
return true;
}
ll get(){
return min(reseven, resodd);
}
};
struct item{
ll w, a, b;
};
vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e){
n = a.size();
c = vector<ll> (n, 0ll);
vector<ll> ans((ll)e.size());
for(auto i : b)
sum += i;
// ans = sum + cost(i)
vector<item> arr(n);
for(int i = 0; i < n; i++)
arr[i] = {w[i], a[i], b[i]};
sort(all(arr), [](item x, item y){
return x.w < y.w;
});
// cout << "arr: \n";
// for(auto i : arr)
// cout << i.w << ' ' << i.a << ' ' << i.b << '\n';
// cout << '\n';
for(int i = 0; i < n; i++)
c[i] = arr[i].a - arr[i].b;
// cout << "c: \n";
// for(auto i : c)
// cout << i << ' ';
// cout << '\n';
for(int i = 0; i < e.size(); i++)
q.push_back({e[i], i});
sort(all(q));
// cout << "q: \n";
// for(auto i : q)
// cout << i.first << ' ' << i.second << '\n';
// cout << '\n';
vector<pii> p;
for(int i = 0; i < n - 1; i++){
p.push_back({i, i + 1});
if(i + 2 < n)
p.push_back({i, i + 2});
}
sort(all(p), [&](pii x, pii y){
return arr[x.second].w - arr[x.first].w < arr[y.second].w - arr[y.first].w;
});
// cout << "p: \n";
// for(auto i : p)
// cout << arr[i.second].w - arr[i.first].w << ' ' << arr[i.first].w << ' ' << arr[i.second].w << ' ' << i.first << ' ' << i.second << '\n';
// cout << '\n';
dsu ds(n);
int i = 0;
for(auto [d, idx] : q){
while(i < p.size() && arr[p[i].second].w - arr[p[i].first].w <= d){
ds.merge(p[i].first, p[i].second);
i++;
}
ans[idx] = sum + ds.get();
}
// for(int i = 0; i < n; i++)
// cout << ds.get(i) << ' ';
// cout << '\n';
// ds.merge(1, 2);
// ds.merge(2, 3);
// // ds.merge(3, 4);
// // ds.merge(0, 1);
// for(int i = 0; i < n; i++)
// cout << ds.get(i) << ' ';
// cout << '\n';
/*
*/
return ans;
}
