색칠된 순열 정렬

시간 제한2초메모리 제한1024 MB

요약

위치마다 색이 칠해진 순열을 정렬할 때, 두 원소 교환(S원)이나 한 색 위치의 재배열(C_i원) 중 골라 드는 최소 비용을 구합니다.

난이도: 보통10점 중 7점
유형: 비트 연산, 그래프, 구현
정답자: 아직 제출이 없습니다

문제

순열 $p_1, p_2, \ldots, p_n$ 이 주어진다. 이 순열은 1부터 $n$ 까지의 정수를 한 번씩 담고 있다. 1부터 $n$ 까지의 각 위치는 $k$ 가지 색 중 하나로 칠해져 있다. 이 순열을 정렬하려고 한다. 다음 두 종류의 연산을 원하는 만큼 적용할 수 있다.

임의의 두 원소를 교환한다. 이 연산의 비용은 $S$ 코인이다.
색 $i$ 를 하나 고르고, 색이 $i$ 인 위치의 원소들을 원하는 대로 다시 배열한다. 이 연산의 비용은 $C_i$ 코인이다.

칠해진 것은 원소가 아니라 위치다. 두 원소를 교환해도 위치의 색은 그대로다. 순열을 정렬하는 데 드는 코인의 최솟값을 구하라.

입력

첫 줄에 테스트 케이스의 개수 $T$ ( $1 \le T \le 10^{3}$ )가 주어진다.

각 테스트 케이스의 첫 줄에는 $n$ 과 $k$ ( $1 \le n \le 10^{5}$ , $1 \le k \le 5$ )가 주어진다. 둘째 줄에는 $S, C_1, C_2, \ldots, C_k$ ( $0 \le S, C_i \le 10^{9}$ )가 주어진다. 셋째 줄에는 순열 $p_1, p_2, \ldots, p_n$ ( $1 \le p_i \le n$ , 모든 $p_i$ 는 서로 다르다)이 주어진다. 넷째 줄에는 각 위치의 색 $col_1, col_2, \ldots, col_n$ ( $1 \le col_i \le k$ )이 주어진다.

모든 테스트 케이스의 $n$ 을 합하면 $10^{5}$ 를 넘지 않는다.

출력

각 테스트 케이스마다 순열을 정렬하는 데 필요한 코인의 최솟값을 한 줄에 하나씩 출력한다.

힌트

첫 번째 테스트 케이스에서는 교환 연산을 3번 적용하면 순열이 정렬된다. $(2, 3, 4, 1) \to (4, 3, 2, 1) \to (4, 2, 3, 1) \to (1, 2, 3, 4)$ 순서로 바뀌며, 총 3코인이 든다. 색 1인 위치의 원소를 모두 재배열해도 되지만 10코인이 들어 더 비싸다.

두 번째 테스트 케이스는 연산 비용만 첫 번째와 다르다. 여기서는 색 1인 위치를 재배열하는 데 1코인만 들므로 이 방법이 더 싸다.

세 번째 테스트 케이스의 최적 순서는 다음과 같다. 색 2인 위치를 재배열해 $(5, 2, 4, 3, 1, 6)$ 을 만든다(1코인). 이어서 $p_3$ 와 $p_4$ 를 교환해 $(5, 2, 3, 4, 1, 6)$ 을 만든다(10코인). 마지막으로 색 1인 위치를 재배열해 $(1, 2, 3, 4, 5, 6)$ 을 만든다(1코인). 합계는 12코인이다.

네 번째 테스트 케이스는 이미 정렬되어 있으므로 코인이 들지 않는다.

예제1

예제 1

입력

4
4 1
1 10
2 3 4 1
1 1 1 1
4 1
10 1
2 3 4 1
1 1 1 1
6 2
10 1 1
5 2 4 6 1 3
1 2 1 2 1 2
4 3
6 7 8 9
1 2 3 4
2 2 3 2

예상 출력