Vera and the Engineering Buildings

The University of Waterloo has $N$ engineering buildings numbered from 1 to $N$. For every $i$ with $2 \le i \le N$ there is a two way bridge between building $i$ and building $x_i$. Two buildings are neighbours when a bridge joins them.

Every building has its own aesthetic value, and no two buildings share a value. A value can be any integer. Measuring a value exactly is hard, so Vera only wants to find one nice building, a building whose aesthetic value is higher than the value of each of its neighbours.

Inspecting building $i$ takes $t_i$ seconds and covers the bridges to all of its neighbours. Once the inspection is over, Vera knows for each neighbour $j$ of building $i$ which of building $i$ and building $j$ has the higher aesthetic value.

Vera picks the next building to inspect after seeing the results of the earlier inspections. Travel time between buildings is ignored. Find the smallest total inspection time that guarantees Vera finds a nice building, whatever the aesthetic values are.

The first line contains one integer $N$ ($2 \le N \le 16$).

The second line contains $N$ integers $t_1, t_2, \dots, t_N$ ($1 \le t_i \le 10^8$).

The third line contains $N - 1$ integers $x_2, x_3, \dots, x_N$ ($1 \le x_i < i$).

Print one line with one integer, the minimum total number of seconds that guarantees a nice building is found.

In the first example, inspecting buildings 1 and 3 guarantees a nice building is found.

In the second example, one optimal strategy always inspects building 3 first.