#include "roads.h"
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <utility>
#include <string>
#include <vector>
#include <bitset>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef vector<int32_t> vi;
typedef vector<ll> vll;
typedef pair<int32_t, int32_t> pii;
#define endl "\n"
#define f0(i,n) for(int32_t i = 0; i < (n); i++)
#define f1(i,n) for(int32_t i = 1; i <= (n); i++)
#define rep0(i,l,r) for(int32_t i=(l); i < (r); i++)
#define rep1(i,l,r) for(int32_t i=(l); i <= (r); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define asrt(v) sort(all(v))
#define dsrt(v) sort(rall(v))
#define revStr(str) string(rall(str))
#define len(a) ((int64_t)(a).size())
#define front_zero(n) __builtin_clzll(n)
#define back_zero(n) __builtin_ctzll(n)
#define total_one(n) __builtin_popcountll(n)
#define lcm(a, b) (((a)*(b))/gcd(a,b))
#define mem(a, b) memset(a, b, sizeof(a))
#define pb push_back
#define pf push_front
#define mp make_pair
#define ff first
#define ss second
#define finish return 0
#define clean fflush(stdout)
#define Inf (int32_t)(1e9)
#define INF (lli)(1e18)
#define Eps (ld)(1e-9)
#define EPS (ld)(1e-18)
#define PI (ld)(3.141592653589793238462643383279502884197169L)
#define MOD (int32_t)(1e9+7)
#define MXN (int32_t)(1e5+7)
template<typename dataType1>
inline void print(dataType1 a) {cout << a << endl;}
template<typename dataType1, typename dataType2>
inline void print(dataType1 a, dataType2 b) {cout << a << " " << b << endl;}
template<typename dataType1, typename dataType2, typename dataType3>
inline void print(dataType1 a, dataType2 b, dataType3 c) {cout << a << " " << b << " " << c << endl;}
template<typename dataType1, typename dataType2, typename dataType3, typename dataType4>
inline void print(dataType1 a, dataType2 b, dataType3 c, dataType4 d) {cout << a << " " << b << " " << c << " " << d << endl;}
template<typename dataType>
inline void printarr(dataType* arr, int32_t n) {f0(i,n) cout << arr[i] << " "; cout << endl;}
template<typename dataType>
inline dataType abs(dataType k) {if (k >= 0) return k; else return (-k);}
template<typename dataType>
inline bool isEqual(dataType a, dataType b) {return (abs((dataType)(a-b)) < 1e-9);}
std::vector<long long>
minimum_closure_costs(int N, std::vector<int> U,
std::vector<int> V,
std::vector<int> W) {
bool star = true;
f0(i, N-1) {
if(U[i] != 0) star = false;
}
if(star) {
sort(all(W));
vll ret(N, 0);
ll sum = 0;
f0(i, N-1) sum += W[i];
f0(i, N) {
ret[i] = sum;
if(i != N-1)
sum -= W[N-i-2];
}
return ret;
}
vll ret(N, 0);
ll sum = 0;
f0(i, N-1) sum += W[i];
ret[0] = sum;
if(N == 2) {
ret[1] = W[0];
return ret;
}
N--;
ll dp[N];
dp[0] = W[0];
dp[1] = max(W[0], W[1]);
for(int i = 2; i < N; i++) {
dp[i] = max(dp[i-1], dp[i-2] + W[i]);
}
ret[1] = sum - dp[N-1];
return ret;
return std::vector<long long>(N, 0);
}
