#include <iostream>
#include <iomanip>
#include <math.h>
#include <cmath>
#include <algorithm>
#include <climits>
#include <functional>
#include <cstring>
#include <string>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <complex>
#include <random>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ms multiset
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define re register
#define ri re int
#define il inline
#define pii pair<int,int>
#define cp complex<double>
#define vi vector<int>
#define ull unsigned long long
#define mem0(x) memset(x,0,sizeof(x))
#define mem0x3f(x) memset(x,0x2f,sizeof(x))
#define int long long
using namespace std;
int f[100002][11],nxt[11],v[100002],w[100002],n,m,sz[100002];
vector<int>c[100002];
inline int r(int x){
	if(x==2)return 2;
	return x^1;
}
vector<pii >g[8];
int d[8],col[8],now;
inline void e(int x,int y,int z){
	g[x].push_back(make_pair(y,z));
	g[y].push_back(make_pair(x,z));
}
int T[2][2][11][11];bool FF;
inline bool dfs(int pos){
	col[pos]=now;if(FF)cerr<<pos<<endl;
	for(pii ii:g[pos]){int i=ii.first;
		if(!d[i]){
			d[i]=d[pos]+ii.second;
			if(!dfs(i))return false;//dfs(i);
		}else if((d[i]^d[pos]^ii.second)&1)return false;
	}
	return true;
}
inline int trans(int a,int b,bool cy,bool cw){
	F(i,1,7)g[i].clear(),d[i]=0;now=0;
	if(a==9)e(1,2,1);
	else if(a==10)e(1,2,0);
	else{
		if(a%3==0)e(1,3,0);
		else if(a%3==1)e(1,3,1);
		if(a/3==0)e(2,3,0);
		else if(a/3==1)e(2,3,1);
	}
	if(b==9)e(4,5,1);
	else if(b==10)e(4,5,0);
	else{
		if(b%3==0)e(4,6,0);
		else if(b%3==1)e(4,6,1);
		if(b/3==0)e(5,6,0);
		else if(b/3==1)e(5,6,1);
	}
	e(3,7,0);
	if(!cy)e(6,7,1);
	if(!cw)e(2,4,1);
	if(a==1&&b==1&&cy==1&&cw==0){
	//	FF=true;
	//	F(i,1,7)for(auto j:g[i])if(j.first>i)cerr<<i<<" "<<j.first<<" "<<j.second<<endl;
	}else FF=false;
	F(i,1,7)if(!d[i]){
		++now;d[i]=1;
		if(!dfs(i))return -1;
	}
	int res=0;
	if(col[1]==col[7]){
		if((d[1]^d[7])&1)res+=1;
	}else res+=2;
	if(col[5]==col[7]){
		if((d[5]^d[7])&1)res+=3;
	}else res+=6;
	if(res==8&&col[1]==col[5]){
		res=10;
		if((d[1]^d[5])&1)--res;
	}
	return res;
}
inline void dfs(int pos,int l,int r){
	if(c[pos].empty()){
		f[pos][0]=0;
		return;
	}
	int now=l;
	bool flag=true;
	for(int i:c[pos]){//cerr<<pos<<" "<<i<<endl;
		dfs(i,now,now+sz[i]-1);
		if(flag){
			F(x,0,10){
				int y=x;
				if(y<9){
					if(y%3==1)--y;
					else if(y%3==0)++y;
					if(y>=3&&y<=5)y-=3;
					else if(y<3)y+=3;
				}
				f[pos][x]=f[i][y];
			}
			F(x,0,10){
				if(x%3<=1&&x<=5){
					f[pos][9+(x%3==x/3)]=min(f[pos][9+(x%3==x/3)],f[i][x]+v[i]);
				}else f[pos][8]=min(f[pos][8],f[i][x]+v[i]);
			}
			flag=false;
		}else{
			mem0x3f(nxt);
			F(cy,0,1)F(cw,0,1){
				int co=cy*v[i]+cw*w[now-1];
				F(x,0,10)F(y,0,10)if(~T[cy][cw][x][y]){
					nxt[T[cy][cw][x][y]]=min(nxt[T[cy][cw][x][y]],f[pos][x]+f[i][y]+co);
				}
			}
			memcpy(f[pos],nxt,sizeof(nxt));
			
		}
//	if(pos==1)F(j,0,10)cerr<<f[pos][j]<<" "<<endl;cerr<<endl;
		now+=sz[i];
	}
}
long long place_police(vector<signed> P, vector<long long> C, vector<long long> W){
	F(i,0,10)F(j,0,10)F(y,0,1)F(z,0,1)T[y][z][i][j]=trans(i,j,y,z);//cerr<<"K";
//	cerr<<T[1][0][1][1]<<endl;
//	F(i,0,10)F(j,0,10)F(y,1,1)F(z,0,1)cerr<<T[y][z][i][j]<<endl;
	mem0x3f(f);
	n=P.size()+1;
	F(i,2,n)c[P[i-2]+1].push_back(i),v[i]=C[i-2];//cerr<<c[10].size()<<endl;
	m=W.size();
	F(i,1,m)w[i]=W[i-1];
	UF(i,n,1){
		for(int j:c[i])sz[i]+=sz[j];
		sz[i]=max(sz[i],1ll);
	}
	dfs(1,1,m);
	int ans=LLONG_MAX;
	F(i,0,8){
		if(i%3==2||i>=6)ans=min(ans,f[1][i]);
		if(i%3!=i/3)ans=min(ans,f[1][i]);
	}
	ans=min(ans,f[1][9]);
    return ans;
}
/*
4
0 9
0 8
0 0
9 9 9




0 1 9
0 2 8
2 3 0
3 4 7
3 5 1
2 6 6
0 7 0
7 8 7
7 9 1
9 10 6

1 4
4 5
5 6
6 8
8 10
*/