É dada uma permutação $p_1,p_2,\ldots,p_n$ dos inteiros de $1$ a $n$. Cada posição de $1$ a $n$ está pintada com uma de $k$ cores. Queremos ordenar a permutação e, para isso, podemos realizar qualquer número de operações dos seguintes tipos:

• Trocar dois elementos quaisquer. Esta operação custa $S$ moedas;
• Escolher uma cor $i$ qualquer e permutar como quiser os elementos nas posições da cor $i$. Esta operação custa $C_i$ moedas.

Observe que são as posições que têm cores, e não os elementos; portanto, ao trocar dois elementos, as posições não mudam de cor.

Encontre o número mínimo de moedas que precisa gastar para ordenar a permutação.

Entrada

A primeira linha contém um inteiro $T$ ($1\le T\le10^3$), o número de casos de teste independentes a processar. Seguem-se as descrições dos casos.

A primeira linha de cada caso contém dois inteiros $n,k$ ($1\le n\le10^5$, $1\le k\le5$), o tamanho da permutação e o número de cores.

A segunda linha de cada caso contém $k+1$ inteiros $S,C_1,C_2,\ldots,C_k$ ($0\le S,C_i\le10^9$), os custos das operações.

A terceira linha de cada caso contém $n$ inteiros $p_1,p_2,\ldots,p_n$ ($1\le p_i\le n$, todos os $p_i$ são distintos), a permutação.

A quarta linha de cada caso contém $n$ inteiros $col_i$ ($1\le col_i\le k$), as cores das posições.

A soma de $n$ em todos os casos de teste de um ficheiro não excede $10^5$.

Saída

Para cada caso de teste, escreva um inteiro: o número mínimo de moedas que precisa gastar para ordenar a permutação.

Exemplos

Entrada 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

Saída 1

3
1
12
0

Nota

No primeiro caso de teste, podemos ordenar a permutação aplicando a operação de troca 3 vezes: $(2,3,4,1)\to(4,3,2,1)\to(4,2,3,1)\to(1,2,3,4)$. Assim gastará 3 moedas.

Outra maneira seria permutar todos os elementos nas posições da cor $1$, mas isso custaria 10 moedas, e podemos fazê-lo por menos.

No segundo caso de teste (que difere do primeiro apenas nos custos das operações), porém, é mais barato simplesmente permutar todos os elementos nas posições da cor $1$, gastando 1 moeda.

No terceiro caso de teste, uma sequência ótima de operações seria:

• Permutar os elementos nas posições da cor $2$ para obter $(5,2,4,3,1,6)$. Esta operação custa 1 moeda.
• Trocar os elementos $p_3,p_4$. A permutação é agora $(5,2,3,4,1,6)$. Esta operação custa 10 moedas.
• Permutar os elementos nas posições da cor $1$ para obter $(1,2,3,4,5,6)$. Esta operação custa 1 moeda.

No total, gastámos 12 moedas.

No quarto caso de teste, a permutação já está ordenada, por isso não precisamos de gastar nada.