#include <bits/stdc++.h>
#include "nile.h"
using namespace std;
vector<long long> calculate_costs(
vector<int> W,
vector<int> A,
vector<int> B,
vector<int> E
) {
int N = W.size();
int Q = E.size();
int t = 0;
for(int i = 0; i < N; i++){
if(A[i] != 2 || B[i] != 1){
t++;
}
}
if(t == 0){
vector<long long> dif(N - 1);
for(int i = 0; i < N - 1; i++){
dif[i] = W[i + 1] - W[i];
}
sort(dif.begin(), dif.end());
vector<long long> rs(Q);
for(int i = 0; i < Q; i++){
int D = E[i];
int pr = upper_bound(dif.begin(), dif.end(), D) - dif.begin();
rs[i] = 2 * N - 2 * pr;
}
return rs;
}
else{
vector<array<int,3>> at(N);
for (int i = 0; i < N; i++) {
at[i] = {W[i], A[i], B[i]};
}
sort(at.begin(), at.end());
long long sm = 0;
for (int i = 0; i < N; i++) {
sm += at[i][1];
}
vector<long long> rs(Q);
for (int qi = 0; qi < Q; qi++) {
int D = E[qi];
vector<long long> dp(N, 0);
for (int i = 0; i < N; i++) {
if (i > 0) dp[i] = dp[i - 1];
for (int j = i - 1; j >= 0; j--) {
if (at[i][0] - at[j][0] > D) break;
long long sv =
(long long)at[i][1] + at[j][1]
- at[i][2] - at[j][2];
if (j > 0)
dp[i] = max(dp[i], dp[j - 1] + sv);
else
dp[i] = max(dp[i], sv);
}
}
rs[qi] = sm - dp[N - 1];
}
return rs;
}
}
