Colourful Permutation Sorting

Time limit2sMemory limit1024 MB

Summary

Sort a permutation whose positions are colored with k colors, using swaps that cost S or permutations of one color class that cost C_i, minimizing total coins.

Level: Medium7 of 10
Topics: Bit manipulation, Graph, Implementation
Solved: No attempts yet

Problem

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. You want to sort the permutation. You 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.

The positions are colored, not the elements. When you swap two elements, the positions keep their colors. Find the minimum number of coins needed to sort the permutation.

Input

The first line contains a single integer $T$ ( $1 \le T \le 10^{3}$ ), the number of test cases.

Each test case starts with a line containing two integers $n$ and $k$ ( $1 \le n \le 10^{5}$ , $1 \le k \le 5$ ). The second line contains $S, C_1, C_2, \ldots, C_k$ ( $0 \le S, C_i \le 10^{9}$ ). The third line contains the permutation $p_1, p_2, \ldots, p_n$ ( $1 \le p_i \le n$ , all $p_i$ are distinct). The fourth line contains the colors $col_1, col_2, \ldots, col_n$ ( $1 \le col_i \le k$ ) of the positions.

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

Output

For each test case, print the minimum number of coins needed to sort the permutation, one per line.

Hint

In the first test case, applying the swap operation 3 times sorts the permutation: $(2, 3, 4, 1) \to (4, 3, 2, 1) \to (4, 2, 3, 1) \to (1, 2, 3, 4)$ . This costs 3 coins. Permuting all elements at color 1 positions also works, but it costs 10 coins, which is more.

The second test case differs from the first only in operation costs. Here permuting the color 1 positions costs 1 coin, which is cheaper.

In the third test case, an optimal sequence is as follows. First, permute the elements at color 2 positions to get $(5, 2, 4, 3, 1, 6)$ , costing 1 coin. Then swap $p_3$ and $p_4$ , costing 10 coins, to get $(5, 2, 3, 4, 1, 6)$ . Finally, permute the elements at color 1 positions to get $(1, 2, 3, 4, 5, 6)$ , costing 1 coin. The total is 12 coins.

In the fourth test case, the permutation is already sorted, so no coins are spent.

Examples1

Example 1

Input

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

Expected output