Bridge Removal

The Coral Islands were once a popular tourist destination. To preserve the natural environment, the government decided to close the islands to visitors and take down every structure people had built there. The hardest part of the work is removing all the bridges that connect the islands.

There are $n$ islands and $n-1$ bridges. The bridges are laid out so that from any island you can reach every other island by crossing one or more bridges. The removal team can start on any island, and it repeats either of the following steps in any order it likes.

• Cross a bridge connected to the current island and move to the island on the other side.
• Remove one bridge connected to the current island, and stay on that island after the removal.

A bridge that has been removed cannot be crossed in either direction. Crossing a bridge takes time proportional to its length, and removing it takes the same time. Compute the shortest time needed to remove all the bridges. The island where the team starts can differ from the island where it finishes.

The input consists of several datasets, at most 100 of them. Each dataset has the following format.

n
p2 p3 ... pn
d2 d3 ... dn

The first integer $n$ ($3 \le n \le 800$) is the number of islands. The islands are numbered from 1 to $n$. The second line contains $n-1$ island numbers $p_i$ ($1 \le p_i < i$), which means that for each $i$ from 2 to $n$, island $i$ and island $p_i$ are connected by a bridge. The third line contains $n-1$ integers $d_i$ ($1 \le d_i \le 100000$). The bridge between island $i$ and island $p_i$ has length $d_i$, so crossing it takes $d_i$ units of time and removing it also takes $d_i$ units of time. With this input format, every island is guaranteed to be reachable from every other island.

The input ends with a line that holds a single zero.

For each dataset, print on one line the minimum number of time units needed to remove all the bridges. Each line must contain no character other than that number.