31154번 - 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.

제한

노트

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.