Problem H
出典

グレースはある科学の本を読もうとしています。 しかし、彼女は、本が参照している出典を常に読むこと、また、その出典の出典とたどって全てを読むことに非常に気をつけています。 そのため、最初は1冊読みたかっただけなのに、かなり多くの本を読んでしまうことが多いのです。 図書館員はグレースの本の借りすぎについて常に文句を言っているので、彼女は今、借りている時間の合計が最小となる読書順を見つけたいと思っています。

彼女が最終的に読まなければならない本が$N$冊あります。 本には$1$から$N$までの番号が付けられており、本$i$は読むのに$k_ i$分かかります。 すべての本$i$には、$F_ i$冊の本を含む引用リストがあります。 グレースが本来読みたい本は、番号$1$のものです。 本$1$から始める前に、グレースはすでに$N$冊の本すべてを借りています。

グレースが本を読む際、彼女は以下のことを行います。

• まず彼女は本を開き、引用リストを読みます。これには1分かかります。

• 続いて彼女はリストに含まれる本を任意の順序で全て読みます。

• 最後に彼女はこの本を読み、図書館に返します。これには$K_ i$分かかります。

あなたは、グレースが最適な順序で本を読む場合の、最小の借りている時間を計算する必要があります。 本によっては、引用リストが空である可能性があります。また、番号$1$以外の本は、1冊の引用リストにだけ記載されています。 引用リストの循環参照はありません。

入力

最初の行は、整数$N$ ($1 \le N \le 100\, 000$)です。 次の$N$行は、それぞれ本$1$から$N$を表します。 それぞれの行には、数値$K_ i$ ($1 \le K_ i \le 1\, 000$)があります。これは、その本を読むのに何分かかるかを表します。 その後に数値$F_ i$ ($0 \le F_ i < N$)が繰り返しあります。これは、本$i$が引用している本の番号を表します。

出力

単一の正の整数で、すべての本を借りている時間の合計の最小値を出力します。

制約

あなたのソリューションは、テストグループのセットでテストされ、それぞれのグループにポイントが定義されています。 各テストグループにはテストケースのセットが含まれています。 テストグループのポイントを得るためには、テストグループ内のすべてのテストケースが成功する必要があります。 あなたの最終的なスコアは、1回の提出での最大スコアとなります。

サンプル1の説明

time 1: open book 1
time 2: open book 2
time 3: open book 4
time 4: close book 4 (borrow time 4 minutes)
time 14: close book 2 (borrow time 14 minutes)
time 15: open book 3
time 16: open book 5
time 17: close book 5 (borrow time 17 minutes)
time 37: close book 3 (borrow time 37 minutes)
time 38: close book 1 (borrow time 38 minutes)