配点 : 600 点

問題文

dwango社員のニワンゴくんは、アプリ開発に携わるエンジニアです。ニワンゴくんは、開発したアプリのビルド・テスト・デプロイなどを毎日行っています。業務を効率化するために、ニワンゴくんはこういった依存関係のあるタスクを適切に実行するプログラムを書くことにしました。

タスクは N 個あり、 i 番目のタスクを実行すると、その結果として x_i MB のデータがディスクに書き込まれます。ただし、タスクは別のタスクに依存していることがあり、全ての依存先タスクの実行結果がディスク上に書き込まれていなければそのタスクは実行できません。 i 番目 (2 \leq i \leq N) のタスクを依存先に持つタスクは a_i です。

N 個のタスクの依存関係は、連結な有向木になることが分かっています。つまり、どのタスクについても、そのタスクを依存先として持つタスクはちょうど1つだけ存在します。ただし、例外となる1番目のタスクはどのタスクからも依存されません。1番目のタスクは、それ以外のすべてのタスクに直接的、あるいは間接的に依存しています。

ニワンゴくんの目的は、1番目のタスクを実行し、その結果をディスク上に書き込むことです。さらにニワンゴくんは、計算資源をできるだけ節約したいと考えました。ニワンゴくんは、任意のタスクを実行した直後に、ディスク上に書き込まれている任意の 0 個以上のタスクの実行結果を選び、削除することができます。また、時間計算量も節約したいので、同じタスクを2回以上実行することはないようにしました。

ニワンゴ君が1番目のタスクの実行結果を得るにはどれだけのディスクが必要でしょうか？適切な順番でタスクの実行および実行結果の削除を行い、その過程での最大のディスク使用量（ディスクに書き込まれている実行結果の量の総和）が最小になるようにしてください。その最小値 (MB) を出力してください。

制約

• 1 \leq N \leq 20
• 1 \leq x_i \leq 1,000,000 (1 \leq i \leq N)
• 1 \leq a_i \leq i - 1 (2 \leq i \leq N)

入力

入力は以下の形式で標準入力から与えられる。

N
x_{1} x_{2} x_{3} ... x_{N} 
a_{2} a_{3} ... a_{N} 

出力

答えを出力せよ。

入力例1

5
3 5 2 4 6
1 1 2 2

出力例1

15

このようにすれば、過程での最大ディスク消費量が15 MBとなります。この入力ではこれが最善です。

入力例2

2
3 5
1

出力例2

8

入力例3

5
1 2 3 4 5
1 2 3 4

出力例3

9