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

Các đảo chủ yếu liên lạc với nhau bằng sóng vô tuyến. Mỗi đảo có một máy phát và một máy thu. 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ừ đúng một đảo cụ thể. Có thể đổi hướng máy thu để thay đổi đảo mà nó nhận sóng.

Hiện tại, máy thu trên đảo \(i\) nhận được sóng từ đảo \(A_i\), với \(A_i \ne i\). Chi phí đổi hướng máy thu trên đảo \(i\) là \(C_i\), không phụ thuộc vào hướng mới, với \(1 \le i \le N\).

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\) nhận được sóng từ đảo \(i\), với \(1 \le i,j \le N\) và \(i \ne j\), thì có thể gửi điện báo từ đảo \(i\) đến đảo \(j\) qua liên lạc vô tuyến. Điện báo cũng có thể được chuyển tiếp qua một số đảo. Cụ thể, với ba đảo phân biệt \(i,j,k\), nếu có thể gửi điện báo từ \(i\) đến \(j\) và từ \(j\) đến \(k\), thì có thể gửi điện báo từ \(i\) đến \(k\). Không thể gửi điện báo bằng phương thức nào khác ngoài liên lạc vô tuyến.

Là bộ trưởng phụ trách thông tin liên lạc 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. Để đạt được điều này, có thể cần đổi hướng máy thu trên một số đảo. Tổng chi phí là tổng chi phí đổi hướng của từng máy thu được thay đổi.

Yêu cầu

Cho số đảo và thông tin về máy thu trên từng đảo. Hãy tính chi phí nhỏ nhấ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 từ đầu vào chuẩn:

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

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa chi phí nhỏ nhấ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.

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(1 \le A_i \le N\) với mọi \(1 \le i \le N\).
• \(A_i \ne i\) với mọi \(1 \le i \le N\).
• \(1 \le C_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le N\).

Các bài toán con

1. 10 điểm: \(N \le 10\).
2. 30 điểm: \(N \le 15\).
3. 30 điểm: \(N \le 3\,000\).
4. 30 điểm: Không có ràng buộc bổ sung.

Ví dụ

4
2 2
1 4
1 3
3 1

4

4
2 2
1 6
1 3
3 1

5

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

4
2 2
1 3
4 2
3 3

4

3
2 1
3 1
1 1

0