Friend

People numbered $0$ to $n-1$ join a social network in stages. At stage $i$, a host already in the network adds person $i$ using one of three protocols. IAmYourFriend makes the newcomer a friend of the host only. MyFriendsAreYourFriends makes the newcomer a friend of each current friend of the host, but not the host. WeAreYourFriends makes the newcomer a friend of the host and of each current friend of the host. Friends cannot both appear in a survey sample. Each person has a confidence value. Find the maximum total confidence of a sample with no friend pair.

The first line contains $n$. The second line lists confidence values. The third line lists host protocol pairs for stages $1$ through $n-1$, where protocol $0,1,2$ match the three rules above.

Print the maximum possible total confidence of a valid sample.

• $2 \leq n \leq 100{,}000$
• $1 \leq$ confidence $\leq 10{,}000$