베라와 공대 건물

워털루 대학교에는 1번부터 $N$번까지 번호가 붙은 공대 건물이 $N$개 있다. $2$ 이상 $N$ 이하인 모든 $i$에 대해 $i$번 건물과 $x_i$번 건물을 잇는 양방향 다리가 하나씩 있다. 다리로 이어진 두 건물을 이웃이라고 한다.

건물마다 미관 점수가 하나씩 있고, 두 건물의 점수가 같은 경우는 없다. 점수는 어떤 정수든 될 수 있다. 점수를 정확히 재기는 어려우므로 베라는 멋진 건물 하나만 찾으려고 한다. 멋진 건물은 이웃한 모든 건물보다 미관 점수가 높은 건물이다.

$i$번 건물을 조사하는 데는 $t_i$초가 걸리며, 조사할 때 그 건물에 연결된 다리를 모두 함께 살펴본다. 조사를 마치면 베라는 $i$번 건물의 이웃 $j$마다 $i$번과 $j$번 중 어느 쪽 미관 점수가 더 높은지 알게 된다.

베라는 앞선 조사 결과를 보고 다음에 조사할 건물을 고른다. 건물 사이를 오가는 시간은 계산하지 않는다. 미관 점수가 어떻게 정해져 있든 베라가 멋진 건물을 반드시 찾아내는 데 필요한 조사 시간의 합이 최소 얼마인지 구하라.

첫째 줄에 정수 $N$이 주어진다. ($2 \le N \le 16$)

둘째 줄에 정수 $t_1, t_2, \dots, t_N$이 주어진다. ($1 \le t_i \le 10^8$)

셋째 줄에 정수 $x_2, x_3, \dots, x_N$이 주어진다. ($1 \le x_i < i$)

멋진 건물을 반드시 찾을 수 있는 최소 조사 시간의 합을 한 줄에 정수 하나로 출력한다.

첫 번째 예제에서는 1번 건물과 3번 건물을 조사하면 멋진 건물을 반드시 찾는다.

두 번째 예제에서는 항상 3번 건물을 먼저 조사하는 방법이 최적 전략 중 하나다.