친구

0부터 $n-1$까지 번호가 붙은 사람들이 단계적으로 소셜 네트워크에 들어온다. 단계 $i$에서 초대자가 새 사람 $i$를 세 가지 프로토콜 중 하나로 추가한다. IAmYourFriend는 초대자와만 친구가 되고, MyFriendsAreYourFriends는 초대자의 친구들과만 친구가 되며, WeAreYourFriends는 초대자와 초대자의 친구들과 모두 친구가 된다. 친구끼리는 같이 설문에 참여할 수 없다. 각 사람의 신뢰도가 주어질 때, 친구가 아닌 표본의 신뢰도 합을 최대화하라.

첫 줄에 $n$이 주어진다. 둘째 줄에 각 사람의 신뢰도가 주어진다. 셋째 줄에 단계 $1$부터 $n-1$까지 host protocol 쌍이 주어진다. 프로토콜 $0,1,2$는 위 세 가지를 뜻한다.

가능한 표본 신뢰도 합의 최댓값을 출력한다.

• $2 \leq n \leq 100{,}000$
• $1 \leq$ 신뢰도 $\leq 10{,}000$