Kepulauan JOI adalah negara kepulauan kecil di Samudra Pasifik. Kepulauan JOI memiliki $N$ pulau yang diberi nomor dari $1$ sampai $N$.

Di Kepulauan JOI, komunikasi antarpulau terutama dilakukan melalui radio. Setiap pulau memiliki satu pemancar dan satu penerima gelombang radio. Pemancar dapat mengirim gelombang ke segala arah, tetapi penerima hanya dapat menerima gelombang dari arah tertentu. Oleh karena itu, setiap penerima hanya dapat menerima gelombang dari satu pulau tertentu. Namun, dengan mengubah arah penerima, kita dapat mengubah pulau asal gelombang yang dapat diterimanya.

Saat ini, penerima di pulau $i$ ($1 \le i \le N$) dapat menerima gelombang dari pulau $A_i$ ($A_i \ne i$). Biaya mengubah arah penerima di pulau $i$ adalah $C_i$, tanpa bergantung pada perubahan arah yang dilakukan.

Kepulauan JOI menyediakan layanan telegram sebagai layanan publik. Jika penerima di pulau $j$ ($1 \le j \le N$, $j \ne i$) dapat menerima gelombang dari pulau $i$ ($1 \le i \le N$), telegram dapat dikirim dari pulau $i$ ke pulau $j$ melalui komunikasi radio. Telegram juga boleh dikirim melalui beberapa pulau perantara. Dengan kata lain, untuk pulau $i$, $j$, $k$ ($1 \le i,j,k \le N$, dan $i,j,k$ saling berbeda), jika telegram dapat dikirim dari pulau $i$ ke pulau $j$ dan dari pulau $j$ ke pulau $k$, maka telegram dapat dikirim dari pulau $i$ ke pulau $k$. Telegram tidak dapat dikirim dengan cara selain komunikasi radio.

Sebagai menteri komunikasi Kepulauan JOI, Anda ingin agar telegram dapat dikirim dari pulau mana pun ke pulau mana pun. Untuk itu, mungkin perlu mengubah arah penerima di beberapa pulau. Biaya mengubah arah penerima di beberapa pulau adalah jumlah biaya perubahan arah masing-masing penerima tersebut.

Hitung biaya minimum yang diperlukan agar telegram dapat dikirim dari pulau mana pun ke pulau mana pun.

Tugas

Diberikan banyaknya pulau di Kepulauan JOI serta informasi tentang penerima di setiap pulau, tulislah program yang mencari biaya minimum agar telegram dapat dikirim dari pulau mana pun ke pulau mana pun.

Masukan

Baca data berikut dari masukan standar.

• Baris pertama berisi bilangan bulat $N$. Ini berarti Kepulauan JOI memiliki $N$ pulau.
• Baris ke-$i$ ($1 \le i \le N$) dari $N$ baris berikutnya berisi bilangan bulat $A_i,C_i$ yang dipisahkan spasi. Ini berarti penerima di pulau $i$ saat ini dapat menerima gelombang dari pulau $A_i$, dan biaya mengubah arahnya adalah $C_i$.

Keluaran

Tuliskan dalam satu baris pada keluaran standar biaya minimum agar telegram dapat dikirim dari pulau mana pun ke pulau mana pun.

Batasan

Semua data masukan memenuhi kondisi berikut.

• $2 \le N \le 100\,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 \le 1\,000\,000\,000$ ($1 \le i \le N$).

Subsoal

Subsoal 1 [10 poin]

• $N \le 10$.

Subsoal 2 [30 poin]

• $N \le 15$.

Subsoal 3 [30 poin]

• $N \le 3\,000$.

Subsoal 4 [30 poin]

Tidak ada batasan tambahan.

Contoh

Masukan 1

4
2 2
1 4
1 3
3 1

Keluaran 1

4

Penjelasan

Ubah arah penerima di pulau 2 agar dapat menerima gelombang dari pulau 4. Dengan begitu, telegram dapat dikirim dari pulau mana pun ke pulau mana pun, dengan biaya 4.

Bagaimanapun arah penerima diubah, biayanya tidak dapat kurang dari 4, sehingga keluarkan 4.

Masukan 2

4
2 2
1 6
1 3
3 1

Keluaran 2

5

Penjelasan

Pertama, ubah arah penerima di pulau 1 agar dapat menerima gelombang dari pulau 4. Selanjutnya, ubah arah penerima di pulau 3 agar dapat menerima gelombang dari pulau 2. Dengan begitu, telegram dapat dikirim dari pulau mana pun ke pulau mana pun, dengan biaya $2+3=5$.

Bagaimanapun arah penerima diubah, biayanya tidak dapat kurang dari 5, sehingga keluarkan 5.

Masukan 3

4
2 2
1 3
4 2
3 3

Keluaran 3

4

Penjelasan

Cukup ubah arah penerima di pulau 1 dan pulau 3.

Masukan 4

3
2 1
3 1
1 1

Keluaran 4

0

Penjelasan

Tidak perlu mengubah arah penerima di pulau mana pun.