#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
struct matching {
vector<vector<int>> g;
vector<int> pa;
vector<int> pb;
vector<int> was;
int n, m;
int res;
int iter;
matching(int _n, int _m) : n(_n), m(_m) {
pa.assign(n, -1);
pb.assign(m, -1);
was.resize(n);
g.resize(n);
res = 0;
iter = 0;
}
void add(int from, int to) {
g[from].emplace_back(to);
}
bool dfs(int v) {
was[v] = iter;
for (int u : g[v]) {
if (pb[u] == -1) {
pa[v] = u;
pb[u] = v;
return true;
}
}
for (int u : g[v]) {
if (was[pb[u]] != iter && dfs(pb[u])) {
pa[v] = u;
pb[u] = v;
return true;
}
}
return false;
}
int solve() {
while (true) {
iter++;
int add = 0;
for (int i = 0; i < n; i++) {
if (pa[i] == -1 && dfs(i)) {
add++;
}
}
if (add == 0) {
break;
}
res += add;
}
return res;
}
};
int findSample(int n, int c[], int h[], int p[]) {
vector<vector<int>> g(n);
for (int i = 1; i < n; i++) {
if (p[i] != 0) {
for (int j : g[h[i]]) {
g[i].emplace_back(j);
g[j].emplace_back(i);
}
}
if (p[i] != 1) {
g[i].emplace_back(h[i]);
g[h[i]].emplace_back(i);
}
}
if (all_of(p + 1, p + n, [&](int x) { return (x == 1); })) {
return accumulate(c, c + n, 0);
} else if (all_of(p + 1, p + n, [&](int x) { return (x == 2); })) {
return *max_element(c, c + n);
} else if (all_of(p + 1, p + n, [&](int x) { return (x == 0); })) {
vector<vector<int>> dp(n, vector<int>(2));
function<void(int)> Dfs = [&](int v) {
dp[v][1] = c[v];
for (int to : g[v]) {
if (dp[to][1] != 0) {
continue;
}
Dfs(to);
dp[v][0] += max(dp[to][0], dp[to][1]);
dp[v][1] += dp[to][0];
}
};
Dfs(0);
return max(dp[0][0], dp[0][1]);
} else if (all_of(c, c + n, [&](int x) { return (x == 1); }) && all_of(p + 1, p + n, [&](int x) { return (x <= 1); })) {
vector<int> depth(n);
function<void(int)> Dfs = [&](int v) {
for (int to : g[v]) {
if (depth[to] != 0) {
continue;
}
depth[to] = depth[v] + 1;
Dfs(to);
}
};
for (int i = 0; i < n; i++) {
if (depth[i] != 0) {
continue;
}
Dfs(i);
}
matching mt(n, n);
for (int i = 0; i < n; i++) {
if (depth[i] % 2 == 1) {
continue;
}
for (int j : g[i]) {
mt.add(i, j);
}
}
return n - mt.solve();
} else {
assert(n <= 10);
int ans = 0;
for (int mask = 0; mask < (1 << n); mask++) {
int t = 0;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
t += c[i];
for (int j : g[i]) {
if (mask & (1 << j)) {
t = (int) -1e9;
break;
}
}
}
}
ans = max(ans, t);
}
return ans;
}
}
#ifdef tabr
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
return 0;
}
#endif
