Archipelag JOI to niewielkie państwo wyspiarskie na Oceanie Spokojnym. Składa się z $N$ wysp ponumerowanych od $1$ do $N$.

Komunikacja między wyspami archipelagu JOI odbywa się głównie drogą radiową. Na każdej wyspie znajduje się jeden nadajnik i jeden odbiornik radiowy. Nadajnik może wysyłać fale we wszystkich kierunkach, ale odbiornik odbiera je tylko z określonego kierunku. Dlatego każdy odbiornik może odbierać fale tylko z jednej określonej wyspy. Zmieniając jednak jego kierunek, można zmienić wyspę, z której odbiera fale.

Obecnie odbiornik na wyspie $i$ ($1\le i\le N$) może odbierać fale z wyspy $A_i$ ($A_i\ne i$). Koszt zmiany kierunku odbiornika na wyspie $i$ wynosi $C_i$, niezależnie od wybranego nowego kierunku.

Archipelag JOI świadczy publiczną usługę przesyłania telegramów. Jeśli odbiornik na wyspie $j$ ($1\le j\le N$, $j\ne i$) może odbierać fale z wyspy $i$ ($1\le i\le N$), można przesłać telegram drogą radiową z wyspy $i$ na wyspę $j$. Telegramy można również przesyłać przez inne wyspy. Dokładniej, dla trzech różnych wysp $i,j,k$ ($1\le i,j,k\le N$), jeśli można przesłać telegram z wyspy $i$ na wyspę $j$ oraz z wyspy $j$ na wyspę $k$, to można go przesłać z wyspy $i$ na wyspę $k$. Nie można przesyłać telegramów inaczej niż drogą radiową.

Jako minister łączności archipelagu JOI chcesz umożliwić przesyłanie telegramów z dowolnej wyspy na dowolną inną. W tym celu może być konieczna zmiana kierunku odbiorników na niektórych wyspach. Koszt zmiany kierunków kilku odbiorników jest sumą kosztów zmiany kierunku każdego z nich.

Oblicz minimalny koszt umożliwienia przesyłania telegramów z dowolnej wyspy na dowolną inną.

Zadanie

Napisz program, który na podstawie liczby wysp archipelagu JOI i informacji o odbiorniku na każdej z nich obliczy minimalny koszt umożliwienia przesyłania telegramów z dowolnej wyspy na dowolną inną.

Wejście

Wczytaj następujące dane ze standardowego wejścia.

• Pierwszy wiersz zawiera liczbę całkowitą $N$, oznaczającą liczbę wysp archipelagu JOI.
• $i$-ty z kolejnych $N$ wierszy ($1\le i\le N$) zawiera dwie liczby całkowite $A_i,C_i$ oddzielone spacją. Oznaczają one, że odbiornik na wyspie $i$ odbiera obecnie fale z wyspy $A_i$, a koszt zmiany jego kierunku wynosi $C_i$.

Wyjście

Wypisz w jednym wierszu standardowego wyjścia minimalny koszt umożliwienia przesyłania telegramów z dowolnej wyspy na dowolną inną.

Ograniczenia

Wszystkie dane wejściowe spełniają następujące warunki.

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

Podzadania

Podzadanie 1 [10 punktów]

• Zachodzi $N\le10$.

Podzadanie 2 [30 punktów]

• Zachodzi $N\le15$.

Podzadanie 3 [30 punktów]

• Zachodzi $N\le3\,000$.

Podzadanie 4 [30 punktów]

Nie ma dodatkowych ograniczeń.

Przykład

Wejście 1

4
2 2
1 4
1 3
3 1

Wyjście 1

4

Uwagi

Zmieniamy kierunek odbiornika na wyspie $2$, aby odbierał fale z wyspy $4$. Wtedy można przesyłać telegramy z dowolnej wyspy na dowolną inną, a koszt wynosi $4$.

Żadna zmiana kierunków odbiorników nie pozwala uzyskać kosztu mniejszego niż $4$, więc należy wypisać 4.

Wejście 2

4
2 2
1 6
1 3
3 1

Wyjście 2

5

Uwagi

Najpierw zmieniamy kierunek odbiornika na wyspie $1$, aby odbierał fale z wyspy $4$. Następnie zmieniamy kierunek odbiornika na wyspie $3$, aby odbierał fale z wyspy $2$. Wtedy można przesyłać telegramy z dowolnej wyspy na dowolną inną, a koszt wynosi $2+3=5$.

Żadna zmiana kierunków odbiorników nie pozwala uzyskać kosztu mniejszego niż $5$, więc należy wypisać 5.

Wejście 3

4
2 2
1 3
4 2
3 3

Wyjście 3

4

Uwagi

Wystarczy zmienić kierunki odbiorników na wyspach $1$ i $3$.

Wejście 4

3
2 1
3 1
1 1

Wyjście 4

0

Uwagi

Nie trzeba zmieniać kierunku odbiornika na żadnej wyspie.