Die JOI-Inseln sind ein kleiner Inselstaat im Pazifik. Es gibt $N$ Inseln, die von $1$ bis $N$ nummeriert sind.

Auf den JOI-Inseln erfolgt die Kommunikation zwischen den Inseln hauptsächlich per Funk. Jede Insel hat genau einen Funksender und einen Funkempfänger. Der Sender kann Signale in alle Richtungen senden, der Empfänger kann jedoch nur Signale aus einer bestimmten Richtung empfangen. Deshalb kann jeder Empfänger nur Signale von genau einer bestimmten Insel empfangen. Durch Ändern der Ausrichtung des Empfängers lässt sich jedoch ändern, von welcher Insel er Signale empfangen kann.

Derzeit kann der Empfänger auf Insel $i$ ($1 \le i \le N$) Signale von Insel $A_i$ ($A_i \ne i$) empfangen. Die Kosten für das Ändern seiner Ausrichtung betragen $C_i$, unabhängig davon, wie die Ausrichtung geändert wird.

Auf den JOI-Inseln wird ein Telegrammdienst als öffentliche Dienstleistung betrieben. Wenn der Empfänger auf Insel $j$ ($1 \le j \le N$, $j \ne i$) Signale von Insel $i$ ($1 \le i \le N$) empfangen kann, kann ein Telegramm per Funk von Insel $i$ zu Insel $j$ gesendet werden. Telegramme dürfen auch über mehrere Inseln weitergeleitet werden. Das heißt: Für paarweise verschiedene Inseln $i,j,k$ ($1 \le i,j,k \le N$) gilt: Wenn ein Telegramm von Insel $i$ zu Insel $j$ und von Insel $j$ zu Insel $k$ gesendet werden kann, kann es auch von Insel $i$ zu Insel $k$ gesendet werden. Telegramme können ausschließlich per Funk gesendet werden.

Als Kommunikationsminister der JOI-Inseln möchtest du erreichen, dass von jeder Insel zu jeder anderen Insel Telegramme gesendet werden können. Dafür musst du möglicherweise die Ausrichtung der Empfänger einiger Inseln ändern. Die Kosten dafür sind die Summe der Kosten für die Ausrichtungsänderung jedes betroffenen Empfängers.

Berechne die minimalen Kosten, um Telegramme von jeder Insel zu jeder anderen Insel senden zu können.

Aufgabe

Gegeben sind die Anzahl der JOI-Inseln und Informationen über den Empfänger jeder Insel. Schreibe ein Programm, das die minimalen Kosten berechnet, um Telegramme von jeder Insel zu jeder anderen Insel senden zu können.

Eingabe

Lies die folgenden Daten von der Standardeingabe.

• Die erste Zeile enthält eine ganze Zahl $N$. Sie gibt an, dass es $N$ JOI-Inseln gibt.
• Die $i$-te Zeile ($1 \le i \le N$) der folgenden $N$ Zeilen enthält die durch ein Leerzeichen getrennten ganzen Zahlen $A_i,C_i$. Dies bedeutet, dass der Empfänger auf Insel $i$ derzeit Signale von Insel $A_i$ empfangen kann und die Kosten für das Ändern seiner Ausrichtung $C_i$ betragen.

Ausgabe

Gib in einer Zeile auf der Standardausgabe die minimalen Kosten aus, um Telegramme von jeder Insel zu jeder anderen Insel senden zu können.

Beschränkungen

Alle Eingabedaten erfüllen die folgenden Bedingungen.

• $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$).

Teilaufgaben

Teilaufgabe 1 [10 Punkte]

• Es gilt $N \le 10$.

Teilaufgabe 2 [30 Punkte]

• Es gilt $N \le 15$.

Teilaufgabe 3 [30 Punkte]

• Es gilt $N \le 3\,000$.

Teilaufgabe 4 [30 Punkte]

Es gibt keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

4
2 2
1 4
1 3
3 1

Ausgabe 1

4

Hinweis

Ändere die Ausrichtung des Empfängers auf Insel $2$, sodass er Signale von Insel $4$ empfangen kann. Dann können von jeder Insel zu jeder anderen Insel Telegramme gesendet werden, und die Kosten betragen $4$.

Da die Kosten bei keiner Änderung der Empfängerausrichtungen kleiner als $4$ sein können, gib $4$ aus.

Eingabe 2

4
2 2
1 6
1 3
3 1

Ausgabe 2

5

Hinweis

Ändere zuerst die Ausrichtung des Empfängers auf Insel $1$, sodass er Signale von Insel $4$ empfangen kann. Ändere anschließend die Ausrichtung des Empfängers auf Insel $3$, sodass er Signale von Insel $2$ empfangen kann. Dann können von jeder Insel zu jeder anderen Insel Telegramme gesendet werden, und die Kosten betragen $2+3=5$.

Da die Kosten bei keiner Änderung der Empfängerausrichtungen kleiner als $5$ sein können, gib $5$ aus.

Eingabe 3

4
2 2
1 3
4 2
3 3

Ausgabe 3

4

Hinweis

Es genügt, die Ausrichtung der Empfänger auf Insel $1$ und Insel $3$ zu ändern.

Eingabe 4

3
2 1
3 1
1 1

Ausgabe 4

0

Hinweis

Die Ausrichtung keines Empfängers muss geändert werden.