#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pl pair<ll, ll>
#define pll pair<ll, pl>
#define ppl pair<pl, pl>
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E) {
// int Q = E.size();
// std::vector<long long> R(Q, 0);
// int n = W.size();
// vector<pair<ll, pair<ll, ll>>> items(n);
// for (int i = 0; i < n; ++i) items[i] = {W[i], {A[i], B[i]}};
// sort(items.begin(), items.end());
// vector<ll> benefit(n);
// for (int i = 0; i < n; ++i) benefit[i] = items[i].second.first - items[i].second.second;
// int idx = 0;
// for (auto &d : E) {
// vector<pll> dp(n + 1, {LLONG_MAX / 2, {LLONG_MAX / 2, -1}}); // {no unused: minCost, {one unused: minCost, one unused: index}}
// dp[0] = {0, {LLONG_MAX / 2, -1}};
// for (int i = 1; i <= n; ++i) {
// dp[i].first = dp[i - 1].first + items[i - 1].second.first;
// if (i < n && items[i].first - items[i - 1].first <= d) {
// // do nothing with current item
// dp[i].second = {dp[i - 1].first + items[i - 1].second.first, i - 1};
// if (dp[i - 1].second.first < LLONG_MAX / 2) {
// pl other = {dp[i - 1].second.first + items[i - 1].second.first, i - 1};
// if (items[i].first - items[dp[i - 1].second.second].first <= d && benefit[dp[i - 1].second.second] > benefit[i - 1]) other.second = dp[i - 1].second.second;
// if (other.first < dp[i].second.first || (other.first == dp[i].second.first && benefit[other.second] > benefit[dp[i].second.second])) dp[i].second = other;
// }
// }
// // combine with one unused
// if (dp[i - 1].second.first < LLONG_MAX / 2) dp[i].first = min(dp[i].first, dp[i - 1].second.first - items[dp[i - 1].second.second].second.first + items[dp[i - 1].second.second].second.second + items[i - 1].second.second);
// }
// R[idx++] = min(dp[n].first, dp[n].second.first);
// }
// return R;
ll minBen = LLONG_MAX / 2;
int n = W.size();
ll res = 0;
for (int i = 0; i < n; ++i) minBen = min(minBen, (ll)A[i] - B[i]), res += B[i];
if (n % 2) res += minBen;
vector<ll> R(E.size(), res);
return R;
}
// vector<ll> testFunc(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
// int minBen = LLONG_MAX / 2;
// int n = W.size();
// ll res = 0;
// for (int i = 0; i < n; ++i) minBen = min(minBen, A[i] - B[i]), res += B[i];
// res += minBen;
// vector<ll> R(E.size(), res);
// return R;
// }
