409102: GYM103438 H Colourful Permutation Sorting

You are given a permutation $$$p_1, p_2, \ldots, p_n$$$ of integers from $$$1$$$ to $$$n$$$. Each position from $$$1$$$ to $$$n$$$ is colored in one of $$$k$$$ colors. We want to sort the permutation, and for that, we can apply any number of operations of the following types:

• Swap any two elements. This operation costs $$$S$$$ coins;
• Choose any color $$$i$$$, and permute the elements on positions of color $$$i$$$ as you wish. This operation costs $$$C_i$$$ coins.

Note that the positions are colored, not the elements, so when you swap two elements, the positions won't change their colors.

Find the minimum number of coins you need to spend to sort the permutation.

The first line of the input contains a single integer $$$T$$$ ($$$1 \le T \le 10^{3}$$$) — the number of independent test cases you need to process. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^{5}$$$, $$$1 \le k \le 5$$$) — the size of the permutation and the number of colors.

The second line of each test case contains $$$(k+1)$$$ integers $$$S, C_1, C_2, \ldots, C_k$$$ ($$$0 \le S, C_i \le 10^9$$$) — the costs of the operations.

The third line of each test case contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, all $$$p_i$$$ are distinct) — the permutation.

The fourth line of each test case contains $$$n$$$ integers $$$col_i$$$ ($$$1 \le col_i \le k$$$) — the colors of the positions.

The sum of $$$n$$$ over all test cases in one file does not exceed $$$10^{5}$$$.

For each test case print a single integer — the minimum number of coins you need to spend to sort the permutation.

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

3
1
12
0

In the first test case, we can sort the permutation by applying the "Swap" operation $$$3$$$ times: $$$(2, 3, 4, 1) \to (4, 3, 2, 1) \to (4, 2, 3, 1) \to (1, 2, 3, 4)$$$. This way you will spend $$$3$$$ coins.

Another way to sort it would be to permute all elements on positions of color $$$1$$$, but this would cost $$$10$$$ coins, and we can do cheaper.

In the second test case (which differs from the first one only in the costs of operations), however, it's cheaper to just permute all elements on positions of color $$$1$$$, spending $$$1$$$ coin on this.

In the third test case, one of the optimal sequences of operations would be the following:

• Permute the elements on positions of color $$$2$$$ to obtain the permutation $$$(5, 2, 4, 3, 1, 6)$$$. This operation costs $$$1$$$ coin.

• Swap elements $$$p_3, p_4$$$. The permutation is now $$$(5, 2, 3, 4, 1, 6)$$$. This operation costs $$$10$$$ coins.

• Permute the elements on positions of color $$$1$$$ to obtain the permutation $$$(1, 2, 3, 4, 5, 6)$$$. This operation costs $$$1$$$ coin.

In total, we spent $$$12$$$ coins.

In the fourth test case, the permutation is already sorted, so we don't have to spend anything.