Problems
Bessie has a special function f(x) that takes an integer in [1, N] and returns an integer in [1, N]. The function is defined by N integers a₁, a₂, …, a_N such that f(x) = aₓ. Bessie wants to make this function idempotent, meaning that for all x ∈ [1, N], f(f(x)) = f(x) must hold. To achieve this, she can change the value of aᵢ to any integer in [1, N] at a cost of cᵢ (1 ≤ cᵢ ≤ 10⁹). Determine the minimum total cost required to make f(x) idempotent.
Input
The first line contains an integer N.
The second line contains N space-separated integers a₁, a₂, …, a_N.
The third line contains N space-separated integers c₁, c₂, …, c_N.
Output
Output a single integer representing the minimum total cost required to make f(x) idempotent.
Subtask
| # | Score | Condition |
|---|---|---|
| #1 | 10 | |
| #2 | 20 | aᵢ ≥ i |
| #3 | 30 | All aᵢ are distinct |
| #4 | 40 | No additional constraints |
Example #1
5
2 4 4 5 3
1 1 1 1 1
3
The initial function is defined as f(1)=2, f(2)=4, f(3)=4, f(4)=5, f(5)=3.
To make f(x) idempotent, we require f(f(x)) = f(x) for all x.
For instance, by changing a₁, a₄, and a₅ to 4, the function becomes:
f(1)=4, f(2)=4, f(3)=4, f(4)=4, f(5)=4
Since f(f(x)) = f(4) = 4 = f(x) for all x, and the total change cost is 1+1+1 = 3, this is optimal.
Example #2
8
1 2 5 5 3 3 4 4
9 9 2 5 9 9 9 9
7
By changing a₃ to 3 and a₄ to 4, the function becomes idempotent.
The total cost is c₃ + c₄ = 2 + 5 = 7, which is the minimum cost.
You must sign in to write code.