You are given a permutation p_1, p_2, \ldots, p_n of integers from to . Each position from to is colored in one of 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 coins;
Choose any color , and permute the elements on positions of color 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 (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 and (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 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 integers col_i (1 \le col_i \le k) — the colors of the positions.
The sum of 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.
Example 1
In the first test case, we can sort the permutation by applying the "Swap" operation 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 coins.
Another way to sort it would be to permute all elements on positions of color , but this would cost 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 , spending 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 to obtain the permutation (5, 2, 4, 3, 1, 6). This operation costs coin.
Swap elements p_3, p_4. The permutation is now (5, 2, 3, 4, 1, 6). This operation costs coins.
Permute the elements on positions of color to obtain the permutation (1, 2, 3, 4, 5, 6). This operation costs coin.
In total, we spent coins.
In the fourth test case, the permutation is already sorted, so we don't have to spend anything.