JOI 諸島是位於太平洋上的小島國。JOI 諸島共有 $N$ 座島嶼，編號為 $1$ 到 $N$。

JOI 諸島的島嶼之間主要透過無線電通訊。每座島上各有一部發射機和一部接收機。發射機能向所有方向發送無線電波，但接收機只能接收來自特定方向的無線電波。因此，每部接收機只能接收來自某一座特定島嶼的無線電波。不過，改變接收機的朝向，就能改變它可以接收哪座島嶼的無線電波。

目前，島嶼 $i$（$1 \le i \le N$）的接收機可以接收來自島嶼 $A_i$（$A_i \ne i$）的無線電波。改變島嶼 $i$ 的接收機朝向所需的成本為 $C_i$，與如何改變朝向無關。

JOI 諸島以公共事業的形式提供電報服務。當島嶼 $j$（$1 \le j \le N$，$j \ne i$）的接收機能接收來自島嶼 $i$（$1 \le i \le N$）的無線電波時，就能透過無線電通訊將電報從島嶼 $i$ 傳送到島嶼 $j$。電報也可以經由數座島嶼轉送。也就是說，對於島嶼 $i$、$j$、$k$（$1 \le i,j,k \le N$，且 $i,j,k$ 互不相同），若能將電報從島嶼 $i$ 傳送到島嶼 $j$，也能從島嶼 $j$ 傳送到島嶼 $k$，就能從島嶼 $i$ 傳送到島嶼 $k$。不能透過無線電通訊以外的方式傳送電報。

身為 JOI 諸島的遞信大臣，你希望能從任意島嶼向任意島嶼傳送電報。為此，可能需要改變某些島嶼接收機的朝向。改變數部接收機朝向的成本，等於改變各部接收機朝向所需成本的總和。

請計算使任意島嶼都能向任意島嶼傳送電報所需的最小成本。

任務

給定 JOI 諸島的島嶼數量以及各島接收機的相關資訊，請撰寫程式，求出使任意島嶼都能向任意島嶼傳送電報所需的最小成本。

輸入格式

從標準輸入讀取以下資料。

• 第一行包含整數 $N$，表示 JOI 諸島共有 $N$ 座島嶼。
• 接下來 $N$ 行中的第 $i$ 行（$1 \le i \le N$）包含以空格分隔的整數 $A_i,C_i$，表示島嶼 $i$ 的接收機目前可以接收來自島嶼 $A_i$ 的無線電波，而改變其朝向的成本為 $C_i$。

輸出格式

向標準輸出印出一行，包含使任意島嶼都能向任意島嶼傳送電報所需的最小成本。

資料範圍

所有輸入資料都滿足以下條件。

• $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$）。

子任務

子任務 1 [10 分]

• 滿足 $N \le 10$。

子任務 2 [30 分]

• 滿足 $N \le 15$。

子任務 3 [30 分]

• 滿足 $N \le 3\,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

說明

不需要改變任何島嶼接收機的朝向。