Se te da una permutación $p_1,p_2,\ldots,p_n$ de los enteros de $1$ a $n$. Cada posición de $1$ a $n$ está pintada de uno de $k$ colores. Queremos ordenar la permutación y, para ello, podemos realizar cualquier número de operaciones de los siguientes tipos:

• Intercambiar dos elementos cualesquiera. Esta operación cuesta $S$ monedas;
• Elegir cualquier color $i$ y permutar como quieras los elementos de las posiciones de color $i$. Esta operación cuesta $C_i$ monedas.

Observa que las posiciones tienen color, no los elementos, por lo que al intercambiar dos elementos las posiciones no cambian de color.

Encuentra el número mínimo de monedas que debes gastar para ordenar la permutación.

Entrada

La primera línea contiene un entero $T$ ($1\le T\le10^3$): el número de casos de prueba independientes que debes procesar. A continuación se describen los casos.

La primera línea de cada caso contiene dos enteros $n,k$ ($1\le n\le10^5$, $1\le k\le5$): el tamaño de la permutación y el número de colores.

La segunda línea de cada caso contiene $k+1$ enteros $S,C_1,C_2,\ldots,C_k$ ($0\le S,C_i\le10^9$): los costes de las operaciones.

La tercera línea de cada caso contiene $n$ enteros $p_1,p_2,\ldots,p_n$ ($1\le p_i\le n$, todos los $p_i$ son distintos): la permutación.

La cuarta línea de cada caso contiene $n$ enteros $col_i$ ($1\le col_i\le k$): los colores de las posiciones.

La suma de $n$ para todos los casos de prueba de un archivo no supera $10^5$.

Salida

Para cada caso de prueba imprime un entero: el número mínimo de monedas que debes gastar para ordenar la permutación.

Ejemplos

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

Salida 1

3
1
12
0

Nota

En el primer caso de prueba podemos ordenar la permutación aplicando la operación de intercambio 3 veces: $(2,3,4,1)\to(4,3,2,1)\to(4,2,3,1)\to(1,2,3,4)$. Así gastarás 3 monedas.

Otra forma sería permutar todos los elementos de las posiciones de color $1$, pero eso costaría 10 monedas y podemos hacerlo más barato.

Sin embargo, en el segundo caso de prueba (que solo difiere del primero en los costes de las operaciones), resulta más barato permutar todos los elementos de las posiciones de color $1$, gastando 1 moneda.

En el tercer caso de prueba, una secuencia óptima de operaciones sería:

• Permutar los elementos de las posiciones de color $2$ para obtener $(5,2,4,3,1,6)$. Esta operación cuesta 1 moneda.
• Intercambiar los elementos $p_3,p_4$. La permutación es ahora $(5,2,3,4,1,6)$. Esta operación cuesta 10 monedas.
• Permutar los elementos de las posiciones de color $1$ para obtener $(1,2,3,4,5,6)$. Esta operación cuesta 1 moneda.

En total hemos gastado 12 monedas.

En el cuarto caso de prueba, la permutación ya está ordenada, así que no tenemos que gastar nada.