JOI 諸島は太平洋に浮かぶ小さな島国である．JOI 諸島には $N$ 個の島があり，$1$ から $N$ までの番号が付けられている．
JOI 諸島では島同士の通信は主に無線によって行われる．それぞれの島には電波の送信機と受信機がひとつずつある．送信機は全方向に電波を送ることができるが，受信機は特定の方向からの電波しか受け取ることができない．そのため，それぞれの受信機は，特定のひとつの島からの電波しか受け取ることができない．ただし，受信機の向きを変えることで，どの島からの電波を受け取ることができるかを変えることができる．
現在，島 $i$（$1\le i\le N$）の受信機は島 $A_i$（$A_i\ne i$）からの電波を受け取ることができる．また，島 $i$ の受信機の向きを変えるのにかかるコストは，どう向きを変えるかによらず，$C_i$ である．
JOI 諸島では，公共事業として電報サービスを行っている．島 $i$（$1\le i\le N$）からの電波を島 $j$（$1\le j\le N$，$j\ne i$）の受信機が受け取ることができるとき，島 $i$ から島 $j$ に無線通信によって電報を送ることができる．また，電報はいくつかの島を経由して送ってもよい．すなわち，島 $i$，島 $j$，島 $k$（$1\le i,j,k\le N$ かつ $i,j,k$ はそれぞれ相異なる）について，島 $i$ から島 $j$ に電報を送ることができ，島 $j$ から島 $k$ に電報を送ることができるとき，島 $i$ から島 $k$ に電報を送ることができる．無線通信以外の方法で電報を送ることはできない．
JOI 諸島の逓信大臣であるあなたは，任意の島から任意の島へ電報を送れるようにしたい．そのためには，いくつかの島の受信機の向きを変える必要があるかもしれない．いくつかの島の受信機の向きを変えるのにかかるコストは，それぞれの受信機の向きを変えるのにかかるコストの総和である．
任意の島から任意の島へ電報を送れるようにするためにかかるコストの最小値を計算せよ．
課題
JOI 諸島の島の数と，それぞれの島の受信機に関する情報が与えられたとき，任意の島から任意の島に電報を送れるようにするためにかかるコストの最小値を求めるプログラムを作成せよ．
入力
標準入力から以下のデータを読み込め．
- 1 行目には，整数 $N$ が書かれている．これは，JOI 諸島には $N$ 個の島があることを表す．
- 続く $N$ 行のうちの $i$ 行目（$1\le i\le N$）には，整数 $A_i,C_i$ が空白を区切りとして書かれている．これは，島 $i$ の受信機は，現在，島 $A_i$ からの電波を受け取ることができ，向きを変えるのにかかるコストが $C_i$ であることを表す．
出力
標準出力に，任意の島から任意の島に電報を送れるようにするためにかかるコストの最小値を 1 行で出力せよ．
制約
すべての入力データは以下の条件を満たす．
- $2\le N\le100\,000$．
- $1\le A_i\le N$（$1\le i\le N$）．
- $A_i\ne i$（$1\le i\le N$）．
- $1\le C_i\le1\,000\,000\,000$（$1\le i\le N$）．
小課題
小課題 1 [10 点]
- $N\le10$ を満たす．
小課題 2 [30 点]
- $N\le15$ を満たす．
小課題 3 [30 点]
- $N\le3\,000$ を満たす．
小課題 4 [30 点]
追加の制限はない．
入出力例
入力 1
4 2 2 1 4 1 3 3 1
出力 1
4
注記
島 $2$ の受信機の向きを変え，島 $4$ からの電波を受け取れるようにする．すると任意の島から任意の島へ電報を送れるようになり，かかったコストは $4$ である．
どのように受信機の向きを変えてもコストが $4$ を下回ることはないので，4 を出力する．
入力 2
4 2 2 1 6 1 3 3 1
出力 2
5
注記
まず，島 $1$ の受信機の向きを変え，島 $4$ からの電波を受け取れるようにする．次に，島 $3$ の受信機の向きを変え，島 $2$ からの電波を受け取れるようにする．すると任意の島から任意の島へ電報を送れるようになり，かかったコストは $2+3=5$ である．
どのように受信機の向きを変えてもコストが $5$ を下回ることはないので，5 を出力する．
入力 3
4 2 2 1 3 4 2 3 3
出力 3
4
注記
島 $1$ と島 $3$ の受信機の向きを変えればよい．
入力 4
3 2 1 3 1 1 1
出力 4
0
注記
どの島の受信機の向きも変えなくてよい．