#include <vector>
#include <algorithm>
#include <cstring>
#include <numeric>
using namespace std;
using i64 = long long;

struct Mat {
  i64 arr[3][3];
  Mat() {
    for (int i = 0; i < 3; i ++)
      for (int j = 0; j < 3; j ++)
        arr[i][j] = -1e18;
  }
  Mat operator * (const Mat &m) const {
    Mat res;
    for (int i = 0; i < 3; i ++)
      for (int j = 0; j < 3; j ++)
        for (int k = 0; k < 3; k ++)
          res.arr[i][k] = max(res.arr[i][k], arr[i][j] + m.arr[j][k]);
    return res;
  }
};

Mat tr[400010];
void mdf(int x, int l, int r, int k, Mat v) {
  if (l == r) {
    tr[x] = v;
    return;
  }
  int m = (l + r) >> 1;
  if (k <= m)
    mdf(x << 1, l, m, k, v);
  else
    mdf(x << 1 | 1, m + 1, r, k, v);
  tr[x] = tr[x << 1] * tr[x << 1 | 1];
}

vector<i64> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
  i64 sumA = 0;
  int n = W.size(), q = E.size();
  for (int i = 0; i < n; i ++) {
    sumA += A[i];
    A[i] = A[i] - B[i];
  }
  vector<int> P(n);
  iota(P.begin(), P.end(), 0);
  sort(P.begin(), P.end(), [&] (int a, int b) {
    return W[a] < W[b];
  });
  vector<pair<int, int>> evts;
  for (int i = 0; i < n; i ++) {
    for (int j: {i - 1, i - 2}) if (j >= 0)
      evts.emplace_back(W[P[i]] - W[P[j]], i);
  }
  sort(evts.begin(), evts.end());
  evts.emplace_back(1e9 + 10, -1);

  vector<i64> res(q);
  vector<int> id(q);
  iota(id.begin(), id.end(), 0);
  sort(id.begin(), id.end(), [&] (int a, int b) {
    return E[a] < E[b];
  });
  int ptr = 0;

  for (int i = 0; i < n; i ++) {
    Mat new_m;
    new_m.arr[0][0] = new_m.arr[0][1] = new_m.arr[1][2] = 0;
    mdf(1, 0, n - 1, i, new_m);
  }

  for (auto e: id) {
    int D = E[e];
    while (evts[ptr].first <= D) {
      auto [_, idx] = evts[ptr ++];
      Mat new_m;
      new_m.arr[0][0] = new_m.arr[0][1] = new_m.arr[1][2] = 0;
      if (W[P[idx]] - W[P[idx - 1]] <= D)
        new_m.arr[1][0] = A[P[idx]] + A[P[idx - 1]];
      if (idx > 1 && W[P[idx]] - W[P[idx - 2]] <= D)
        new_m.arr[2][0] = A[P[idx]] + A[P[idx - 2]];
      mdf(1, 0, n - 1, idx, new_m);
    }
    res[e] = sumA - tr[1].arr[0][0];
  }
  return res;
}