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

說明

唔使改變任何一個島嘅接收機方向。