#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, ll> pil;
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
int n = W.size();
int q = E.size();
vector<vector<int>> arr(n, vector<int>(3));
for (int i = 0; i < n; i++) {
arr[i][0] = W[i];
arr[i][1] = A[i];
arr[i][2] = B[i];
}
sort(arr.begin(), arr.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
});
vector<ll> ans(q);
for (int qi = 0; qi < q; qi++) {
int d = E[qi];
ll sum = 0;
vector<ll> dp(n);
queue<pil> q;
multiset<ll> qVal;
for (int i = 0; i < n; i++) {
int w = arr[i][0], a = arr[i][1], b = arr[i][2];
while (!q.empty() && q.front().first < w - d) {
auto [w2, val] = q.front();
q.pop();
qVal.erase(qVal.find(val));
}
ll last = i == 0 ? 0 : dp[i - 1];
dp[i] = last + a;
if (!q.empty()) {
dp[i] = min(dp[i], *qVal.begin() + sum + b);
}
sum += a;
ll val = last + b - sum;
q.push({w, val});
qVal.insert(val);
}
ans[qi] = dp[n - 1];
}
return ans;
}
// int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// int n, q;
// cin >> n >> q;
// vector<int> W(n), A(n), B(n), E(q);
// for (int i = 0; i < n; i++) {
// cin >> W[i];
// }
// for (int i = 0; i < n; i++) {
// cin >> A[i];
// }
// for (int i = 0; i < n; i++) {
// cin >> B[i];
// }
// for (int i = 0; i < q; i++) {
// cin >> E[i];
// }
// vector<ll> result = calculate_costs(W, A, B, E);
// for (ll cost : result) {
// cout << cost << "\n";
// }
// return 0;
// }
