#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
#define REP(a,b,c) for(int a=b;a<c;a++)
#define F first
#define S second
#define PB push_back
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
vii a;
// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
a.resize(n);
a[0].PB(1);a[1].PB(0);
REP(i,1,n-1){
if(protocol[i]==0||protocol[i]==2){
a[i-1].PB(i);
a[i].PB(i-1);
}
if(protocol[i]==1||protocol[i]==2){
for(auto u:a[i-1]){
a[u].PB(i);
a[i].PB(u);
}
}
}
vi t(n,-1);
t[0]=0;
queue<pi> pq;
pq.push({0,0});
while(!pq.empty()){
int x=pq.front().F;
pq.pop();
for(auto u:a[x])if(t[u]==-1){
t[u]=1-t[x];
pq.push({u,t[u]});
}
}
int l=0,r=0;
REP(i,0,n){
if(t[i]==0)l+=confidence[i];
else r+=confidence[i];
}
return max(l,r);
}
