404146: GYM101431 E Vera and Engineering Buildings

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. Vera and Engineering Buildingstime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

There are N engineering buildings at the University of Waterloo numbered from 1 to N. For i ≥ 2, there is a two-way bridge from building i to building xi. Two buildings are called neighbours if there is a bridge between them.

Each building has a unique aesthetic value which can be any integer. It is difficult to determine the exact aesthetic value of a building, so Vera would like to find a nice building, one that has higher aesthetic value than all of its neighbours. It takes Vera ti seconds to inspect building i and the bridges to all of its neighbours. After the inspection, for each neighbour j of building i, Vera will know which of building i or j has higher aesthetic value.

What is the minimum total seconds such that it is guaranteed that Vera can find a nice building in that time no matter what the aesthetic values are? Vera can decide which building to inspect next based on the results of previous inspections. Ignore the time needed to travel between buildings.

Input

Line 1 contains integer N (2 ≤ N ≤ 16).

Line 2 contains N integers t1, ..., tN (1 ≤ ti ≤ 108).

Line 3 contains N - 1 integers x2, ..., xN (1 ≤ xi < i).

Output

Print one line with one integer, the minimum total seconds that guarantees a nice building can be found.

ExamplesInput
3
10 40 20
1 2
Output
30
Input
5
2 4 1 2 1
1 1 2 2
Output
5
Note

For the first example, inspecting buildings 1 and 3 guarantees a nice building will be found.

For the second example, one optimal strategy is to always inspect building 3 first.

加入题单

上一题 下一题 算法标签: