Bessie có một hàm đặc biệt \(f(x)\) nhận đầu vào là một số nguyên trong \([1,N]\) và trả về một số nguyên trong \([1,N]\) (\(1\le N\le 2\cdot 10^5\)). Hàm \(f(x)\) được định nghĩa bởi \(N\) số nguyên \(a_1\ldots a_N\), trong đó \(f(x)=a_x\) (\(1\le a_i\le N\)).

Bessie muốn hàm này có tính lũy đẳng. Nói cách khác, nó phải thỏa mãn \(f(f(x))=f(x)\) với mọi số nguyên \(x\in[1,N]\).

Với chi phí \(c_i\), Bessie có thể thay đổi giá trị của \(a_i\) thành bất kỳ số nguyên nào trong \([1,N]\) (\(1\le c_i\le 10^9\)). Hãy xác định tổng chi phí tối thiểu Bessie cần trả để làm cho \(f(x)\) có tính lũy đẳng.

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách \(a_1,a_2,\dots,a_N\).

Dòng thứ ba chứa \(N\) số nguyên cách nhau bởi dấu cách \(c_1,c_2,\dots,c_N\).

Dữ liệu ra

In ra tổng chi phí tối thiểu Bessie cần trả để làm cho \(f(x)\) có tính lũy đẳng.

Ví dụ

5
2 4 4 5 3
1 1 1 1 1

3

8
1 2 5 5 3 3 4 4
9 9 2 5 9 9 9 9

7

Phân nhóm

• Dữ liệu 3: \(N\le 20\).
• Dữ liệu 4–9: \(a_i\ge i\).
• Dữ liệu 10–15: Mọi \(a_i\) đều phân biệt.
• Dữ liệu 16–21: Không có ràng buộc bổ sung.

Ngoài ra, trong mỗi phân nhóm trong số ba phân nhóm cuối, nửa đầu số test sẽ thỏa mãn \(c_i=1\) với mọi \(i\).

Nguồn

USACO 2025 February Contest, Gold — Bessie's Function. Tác giả: Avnith Vijayram.

https://usaco.org/index.php?page=viewproblem2&cpid=1497