#include <bits/stdc++.h>
using namespace std;
//#define LOCAL
#define FOR(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n, m) for (int i = n; i <= m; ++i)
#define REPR(i, n, m) for (int i = n; i >= m; --i)
#define FORR(x, a) for (auto& x : a)
#define FORR2(x, y, a) for (auto& [x, y] : a)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(a) ((int)a.size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
const int INF = 1e9;
const ll LLINF = 1e18;
vl calculate_costs(vi W, vi A, vi B, vi E) {
int n = SZ(W);
vector<pair<ll, pll>> arr(n);
FOR(i, n) arr[i] = {W[i], {A[i], B[i]}};
sort(ALL(arr));
vl ans;
FORR(d, E) {
vl a, b, w;
auto checkSeg = [&]() -> ll {
int m = SZ(a);
ll cost = accumulate(ALL(b), 0ll);
if (m%2 == 0) return cost;
else {
ll mn = LLINF;
for (int i = 0; i < m; i += 2) mn = min(mn, cost-b[i]+a[i]);
for (int i = 1; i < m; i += 2) if (abs(w[i-1]-w[i+1]) <= d) mn = min(mn, cost-b[i]+a[i]);
return mn;
}
};
ans.push_back(0);
FOR(i, n) {
w.push_back(arr[i].fi);
a.push_back(arr[i].se.fi);
b.push_back(arr[i].se.se);
if (i == n-1 || abs(arr[i].fi-arr[i+1].fi) > d) {
ans.back() += checkSeg();
w.clear();
a.clear();
b.clear();
}
}
}
return ans;
}
#ifdef LOCAL
int main() {
vl ans = calculate_costs(
{15, 12, 2, 10, 21},
{5, 4, 5, 6, 3},
{1, 2, 2, 3, 2},
{5, 9, 1}
);
FORR(x, ans) cout << x << endl;
return 0;
}
#endif
