\(N\) người bạn của Bessie \((2\leq N \leq 10^5)\) đều sở hữu trang trại của riêng mình. Với mỗi \(1\leq i\leq N\), con bò \(𝑖\) muốn đến thăm con bò \(a_i (a_i≠i)\).

Cho một hoán vị \((p_1,p_2,…,p_N)\) của \(1 … 𝑁\), các lượt thăm diễn ra như sau.

Đối với mỗi \(i\) từ \(1\) đến \(N\):

• Nếu con bò \(a_{p_i}\) đã rời khỏi trang trại của mình thì con bò \(p_i\) vẫn ở lại trang trại của mình.
• Nếu không, con bò \(p_i\) sẽ rời trang trại của mình để đến thăm trang trại của con bò \(a_{p_i}\). Lần ghé thăm này khiến tiếng "moo" vui vẻ được kêu lên \(v_{p_i}\) lần \((0 \leq v_{p_i}\leq 10^9)\).

Tính số lượng moos tối đa có thể có sau tất cả các lượt thăm nếu chọn hoán vị \(p\) hợp lý.

Input

• Dòng đầu tiên chứa số \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên cách nhau bằng dấu cách \(a_i\) và \(v_i\).

Output

Kết quả bài toán.

Scoring

• Subtask \(1\): \(a_i \ne a_j\) với mọi \(i \ne j\).
• Subtask \(2\): \(N \leq 10^3\)
• Subtask \(3\): Không có điều kiện gì thêm.

Example

4
2 10
3 20
4 30
1 40

90