Các Chuyến Thăm

Có $N$ con bò ($2\le N\le {10}^5$), mỗi con sở hữu một trang trại. Bò $i$ muốn đến thăm bò $a_i$ ($a_i\ne i$). Cho một hoán vị $p$ của $1$ đến $N$, các chuyến thăm diễn ra tuần tự:

Với mỗi $i$ từ $1$ đến $N$:

• Nếu bò $a_{p_i}$ đã rời đi, bò $p_i$ ở nhà
• Ngược lại, bò $p_i$ rời đi thăm trang trại của bò $a_{p_i}$, tạo ra $v_{p_i}$ tiếng kêu

Tìm hoán vị $p$ sao cho tổng số tiếng kêu là lớn nhất.

Dữ liệu vào

• Dòng 1: Số nguyên $N$
• $N$ dòng tiếp theo: Hai số nguyên $a_i$ và $v_i$ ($0\le v_i\le {10}^9$)

Dữ liệu ra

Một số nguyên duy nhất — tổng số tiếng kêu tối đa.

Ràng buộc

• $2\le N\le {10}^5$
• $a_i\ne i$
• Test 2-3: $a_i\ne a_j$ với mọi $i\ne j$
• Test 4-7: $N\le {10}^3$
• Test 8-11: Không có ràng buộc thêm

Ví dụ