#include "nile.h"
#include "bits/stdc++.h"
using namespace std;
struct Artefacto{
long long Peso, a, b;
};
bool operator<(const Artefacto& a, const Artefacto& b){
return a.a - a.b > b.a - b.b;
}
vector<Artefacto> Per__es_clave;
vector< vector<long long> > PD;
long long Resolver(long long i, long long Saltado){
if(i == Per__es_clave.size()){
if(Saltado == 1) return 0;
else return 2222222222222222;
}
if(i == Per__es_clave.size() - 1) return Per__es_clave[i].a;
if(PD[i][Saltado] != -2) return PD[i][Saltado];
return PD[i][Saltado] = min(Resolver(i + 2, Saltado) + Per__es_clave[i].b + Per__es_clave[i + 1].b, Resolver(i + 1, 1) + Per__es_clave[i].a);
}
vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e) {
int n = a.size(), q = e.size();
bool F_cil = 1;
for(long long i = 0; i < n; i++){
Artefacto Nuevo;
Nuevo.Peso = w[i];
if(w[i] != 1) F_cil = 0;
Nuevo.a = a[i];
Nuevo.b = b[i];
Per__es_clave.push_back(Nuevo);
}
sort(Per__es_clave.begin(), Per__es_clave.end());
long long r = 0;
if(F_cil){
for(long long i = 0; i < n; i++){
if(i + 1 == n) r += Per__es_clave[i].a;
else r += Per__es_clave[i].b + Per__es_clave[i + 1].b;
i++;
}
return vector<long long>(q, r);
}
long long Menor = 2222222222222222;
for(long long i = 0; i < n; i++){
Menor = min(Per__es_clave[i].a - Per__es_clave[i].b, Menor);
r += Per__es_clave[i].b;
}
PD.assign(n, vector<long long>(2, -2));
if(n % 2 == 0) return vector<long long>(q, r);
else {
vector<long long> Retorno;
for(long long i = 0; i < q; i++){
long long v = e[i];
//cerr<<v<<"\n";
if(v >= 2) Retorno.push_back(r + Menor);
else Retorno.push_back(Resolver(0, 0));
}
return Retorno;
}
}
