문제
Bessie는 특수 함수 f(x)를 가지고 있습니다. f(x)는 [1, N]의 정수를 입력받아 [1, N]의 정수를 반환하며, N개의 정수 a₁, a₂, …, a_N으로 정의되어 있어 f(x) = aₓ입니다. Bessie는 이 함수가 idempotent, 즉 모든 x ∈ [1, N]에 대해 f(f(x)) = f(x)가 성립하도록 만들고자 합니다. 이를 위해, 각 aᵢ의 값을 [1, N] 내의 임의의 정수로 변경할 수 있으며, 변경 비용은 각각 cᵢ (1 ≤ cᵢ ≤ 10⁹)입니다. 목표는 f(x)가 idempotent하도록 만드는 데 필요한 최소 총 비용을 구하는 것입니다.
입력
첫 번째 줄에 정수 N이 주어집니다.
두 번째 줄에는 N개의 정수 a₁, a₂, …, a_N이 공백으로 구분되어 주어집니다.
세 번째 줄에는 N개의 정수 c₁, c₂, …, c_N이 공백으로 구분되어 주어집니다.
출력
f(x)가 idempotent하도록 만드는 데 필요한 최소 총 비용을 출력합니다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 10점 | |
| #2 | 20점 | aᵢ ≥ i |
| #3 | 30점 | 모든 aᵢ가 서로 다름 |
| #4 | 40점 | 추가 제약 조건 없음 |
예제1
5
2 4 4 5 3
1 1 1 1 1
3
초기 함수는 f(1)=2, f(2)=4, f(3)=4, f(4)=5, f(5)=3입니다.
f(x)가 idempotent하기 위해서는 모든 x에 대해 f(f(x)) = f(x)가 되어야 합니다.
예를 들어, a₁, a₄, a₅를 각각 4로 변경하면 함수는 다음과 같이 변합니다:
f(1)=4, f(2)=4, f(3)=4, f(4)=4, f(5)=4
모든 x에 대해 f(f(x)) = f(4) = 4 = f(x)가 성립하며, 변경 비용은 1+1+1 = 3으로 최소임을 알 수 있습니다.
예제2
8
1 2 5 5 3 3 4 4
9 9 2 5 9 9 9 9
7
a₃와 a₄를 각각 3과 4로 변경하면, f(x)가 idempotent해집니다.
변경 비용은 c₃ + c₄ = 2 + 5 = 7로, 최소 비용입니다.