Maximizing the Sum of Happiness in Problem Solving

You are given n problems. For each problem i (1-indexed), you are given an interestingness value \(a_i\). For every problem \(i\) with \(2 \le i \le n\), there is a dependency on problem \(fa_i\) (with \(1 \le fa_i < i\)); that is, you must solve problem \(fa_i\) before solving problem \(i\). It is guaranteed that every problem appears exactly once in these dependency relations, so the dependencies form a tree with problem 1 as the root.

You start with an initial happiness that is considered \(+\infty\). When you solve a problem i while your current happiness is \(k\), your happiness is updated to \[ \min(k,a_i), \] and you add this value immediately to a running total. The process must begin with problem 1 and you cannot solve any problem more than once. Your task is to choose an order to solve all the problems (respecting the dependency constraints) so that the sum of your happiness after each problem is maximized.

Note: If a problem does not decrease your current happiness (i.e. \(a_i \geq k\)), then solving it will add \(k\) to the sum and your current happiness remains \(k\). However, if \(a_i < k\), your happiness drops to \(a_i\) and every subsequent addition will use this lower value. Thus, it is optimal to postpone any problem that would lower your current happiness as long as possible.

inputFormat

The input begins with a single integer n representing the number of problems.

The second line contains n space-separated integers \(a_1, a_2, \ldots, a_n\) representing the interestingness of each problem.

The following line (or n - 1 lines) contains n - 1 space-separated integers \(fa_2, fa_3, \ldots, fa_n\) where each \(fa_i\) (for \(2 \le i \le n\)) indicates that problem i depends on problem \(fa_i\) (with \(1 \le fa_i < i\)).

outputFormat

Output a single integer: the maximum possible sum of happiness after solving all the problems in an order that respects the dependency constraints.

sample

3
5 3 6
1 1

13