#include <bits/stdc++.h>
#define task "TEST"
#define task2 "A"
#define pl pair<ll, ll>
#define VI vector<int>
#define VL vector<ll>
#define pf push_front
#define pb push_back
#define pob pop_back
#define pof pop_front
#define mp make_pair
#define fi first
#define se second
#define FOR(i, a, b, c) for (int i=a; i<=b; i+=c)
#define FORE(i, a, b, c) for (int i=a; i>=b; i+=c)
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int Mod = 1e9+7;
const int maxn = 2e5;
const ll Inf = 1e16;
ll n, q, dp[maxn+1];
struct Object {
ll w, a, b;
bool operator < (Object other) {
return w < other.w;
};
};
Object O[maxn+1];
bool ck[maxn+1];
VL calculate_costs(VI W, VI A, VI B, VI E) {
q = E.size(); n = W.size(); VL ret;
ll sum = 0;
FOR(i, 0, n-1, 1) O[i+1] = {W[i], A[i], B[i]};
sort(O + 1, O + n + 1);
//FOR(i, 1, n, 1) cout << O[i].a << " ";
FOR(i, 0, q-1, 1) {
memset(dp, 0x3f, sizeof(dp)); dp[1] = A[0]; dp[0] = 0;
FOR(j, 1, n-1, 1) {
FOR(k, j+1, min((ll)j+2, n), 1) {
dp[k] = min(dp[k], dp[k-1] + O[k].a);
if (abs(O[j].w - O[k].w) > E[i]) break;
if (k == j + 1) dp[k] = min(dp[k], dp[j-1] + O[j].b + O[j+1].b);
else dp[k] = min(dp[k], dp[j-1] + O[j].b + O[j+1].a + O[j+2].b);
}
}
/*FOR(j, 1, n, 1) cout << dp[j] << " ";
cout << '\n';*/
ret.pb(dp[n]);
}
return ret;
}
/*void Read()
{
//15 12 2 10 21
//4 2 3 3 1
}
void Solve()
{
for (auto p : calculate_costs({15, 12, 2, 10, 21}, {5, 4, 5, 6, 3}, {1, 2, 2, 3, 2}, {5, 9, 1})) cout << p << '\n';
}
int main()
{
if (fopen (task".inp", "r")) {
freopen (task".inp", "r", stdin);
freopen (task".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
for (t=1; t--;)
{
Read(); Solve();
}
}*/
