Quần đảo JOI là một quốc đảo nhỏ trên Thái Bình Dương. Quần đảo JOI có $N$ hòn đảo, được đánh số từ $1$ đến $N$.

Ở quần đảo JOI, các đảo liên lạc với nhau chủ yếu bằng sóng vô tuyến. Mỗi đảo có một máy phát và một máy thu sóng vô tuyến. Máy phát có thể phát sóng theo mọi hướng, nhưng máy thu chỉ nhận được sóng từ một hướng nhất định. Vì vậy, mỗi máy thu chỉ nhận được sóng từ một hòn đảo cụ thể. Tuy nhiên, bằng cách đổi hướng máy thu, ta có thể thay đổi hòn đảo mà máy thu nhận được sóng từ đó.

Hiện tại, máy thu trên đảo $i$ ($1 \le i \le N$) nhận được sóng từ đảo $A_i$ ($A_i \ne i$). Chi phí đổi hướng máy thu trên đảo $i$ là $C_i$, bất kể đổi hướng như thế nào.

Quần đảo JOI cung cấp dịch vụ điện báo như một dịch vụ công. Nếu máy thu trên đảo $j$ ($1 \le j \le N$, $j \ne i$) nhận được sóng từ đảo $i$ ($1 \le i \le N$), ta có thể gửi điện báo từ đảo $i$ đến đảo $j$ bằng liên lạc vô tuyến. Điện báo cũng có thể được gửi qua một số đảo trung gian. Cụ thể, với các đảo $i,j,k$ ($1 \le i,j,k \le N$ và $i,j,k$ đôi một khác nhau), nếu có thể gửi điện báo từ đảo $i$ đến đảo $j$ và từ đảo $j$ đến đảo $k$, thì có thể gửi điện báo từ đảo $i$ đến đảo $k$. Không thể gửi điện báo bằng cách nào khác ngoài liên lạc vô tuyến.

Là bộ trưởng bưu chính viễn thông của quần đảo JOI, bạn muốn có thể gửi điện báo từ bất kỳ đảo nào đến bất kỳ đảo nào khác. Để làm được điều đó, có thể cần đổi hướng máy thu trên một số đảo. Chi phí đổi hướng máy thu trên một số đảo là tổng chi phí đổi hướng của từng máy thu đó.

Hãy tính chi phí nhỏ nhất cần thiết để có thể gửi điện báo từ bất kỳ đảo nào đến bất kỳ đảo nào khác.

Yêu cầu

Cho số lượng đảo của quần đảo JOI và thông tin về máy thu trên mỗi đảo, hãy viết chương trình tìm chi phí nhỏ nhất cần thiết để có thể gửi điện báo từ bất kỳ đảo nào đến bất kỳ đảo nào khác.

Dữ liệu vào

Đọc dữ liệu sau từ đầu vào chuẩn.

• Dòng đầu tiên chứa số nguyên $N$, cho biết quần đảo JOI có $N$ hòn đảo.
• Dòng thứ $i$ ($1 \le i \le N$) trong $N$ dòng tiếp theo chứa các số nguyên $A_i,C_i$, cách nhau bởi dấu cách. Điều này có nghĩa là máy thu trên đảo $i$ hiện nhận được sóng từ đảo $A_i$, và chi phí đổi hướng máy thu là $C_i$.

Dữ liệu ra

Ghi ra đầu ra chuẩn trên một dòng chi phí nhỏ nhất cần thiết để có thể gửi điện báo từ bất kỳ đảo nào đến bất kỳ đảo nào khác.

Giới hạn

Tất cả dữ liệu vào thỏa mãn các điều kiện sau.

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

Nhiệm vụ con

Nhiệm vụ con 1 [10 điểm]

• $N \le 10$.

Nhiệm vụ con 2 [30 điểm]

• $N \le 15$.

Nhiệm vụ con 3 [30 điểm]

• $N \le 3\,000$.

Nhiệm vụ con 4 [30 điểm]

Không có giới hạn bổ sung.

Ví dụ

Dữ liệu vào 1

4
2 2
1 4
1 3
3 1

Dữ liệu ra 1

4

Ghi chú

Đổi hướng máy thu trên đảo $2$ để nhận được sóng từ đảo $4$. Khi đó có thể gửi điện báo từ bất kỳ đảo nào đến bất kỳ đảo nào khác, với chi phí $4$.

Không có cách đổi hướng máy thu nào có chi phí nhỏ hơn $4$, nên kết quả là $4$.

Dữ liệu vào 2

4
2 2
1 6
1 3
3 1

Dữ liệu ra 2

5

Ghi chú

Đầu tiên, đổi hướng máy thu trên đảo $1$ để nhận được sóng từ đảo $4$. Tiếp theo, đổi hướng máy thu trên đảo $3$ để nhận được sóng từ đảo $2$. Khi đó có thể gửi điện báo từ bất kỳ đảo nào đến bất kỳ đảo nào khác, với chi phí $2+3=5$.

Không có cách đổi hướng máy thu nào có chi phí nhỏ hơn $5$, nên kết quả là $5$.

Dữ liệu vào 3

4
2 2
1 3
4 2
3 3

Dữ liệu ra 3

4

Ghi chú

Chỉ cần đổi hướng máy thu trên đảo $1$ và đảo $3$.

Dữ liệu vào 4

3
2 1
3 1
1 1

Dữ liệu ra 4

0

Ghi chú

Không cần đổi hướng máy thu trên bất kỳ đảo nào.