Bessie has a special function f(x) that takes as input an integer in [1,N]
and returns an integer in [1,N] (1≤N≤2⋅105). Her function f(x) is defined by N
integers a1…aN where f(x)=ax (1≤ai≤N).
Bessie wants this function to be idempotent. In other words, it should satisfy f(f(x))=f(x)for all integers x∈[1,N].
For a cost of ci, Bessie can change the value of ai to any integer in [1,N] (1≤ci≤109). Determine the minimum total cost Bessie needs to make f(x)
idempotent.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N.
The second line contains N
space-separated integers a1,a2,…,aN.
The third line contains N space-separated integers c1,c2,…,cN.
OUTPUT FORMAT (print output to the terminal / stdout):
Output the minimum total cost Bessie needs to make f(x) idempotent.
SAMPLE INPUT:
5
2 4 4 5 3
1 1 1 1 1
SAMPLE OUTPUT:
3
We can change a1=4, a4=4, a5=4. Since all ci equal one, the total cost is equal to 3
, the number of changes. It can be shown that there is no solution with only 2
or fewer changes.
SAMPLE INPUT:
8
1 2 5 5 3 3 4 4
9 9 2 5 9 9 9 9
SAMPLE OUTPUT:
7
We change a3=3 and a4=4. The total cost is 2+5=7.
SCORING:
Subtasks:
Input 3: N≤20
Inputs 4-9:ai≥i
Inputs 10-15: All aiare distinct.
Inputs 16-21: No additional constraints.
Additionally, in each of the last three subtasks, the first half of tests will satisfy ci=1 for all i.
Problem credits: Avnith Vijayram
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
