On vous donne une permutation $p_1,p_2,\ldots,p_n$ des entiers de $1$ à $n$. Chaque position de $1$ à $n$ est coloriée avec l'une de $k$ couleurs. Nous voulons trier la permutation et pouvons pour cela effectuer un nombre quelconque d'opérations des types suivants :

• Échanger deux éléments quelconques. Cette opération coûte $S$ pièces ;
• Choisir une couleur $i$ quelconque et permuter à volonté les éléments aux positions de couleur $i$. Cette opération coûte $C_i$ pièces.

Notez que ce sont les positions qui sont coloriées, et non les éléments : lorsque vous échangez deux éléments, les positions ne changent donc pas de couleur.

Trouvez le nombre minimal de pièces à dépenser pour trier la permutation.

Entrée

La première ligne contient un entier $T$ ($1\le T\le10^3$), le nombre de cas de test indépendants à traiter. Les descriptions des cas suivent.

La première ligne de chaque cas contient deux entiers $n,k$ ($1\le n\le10^5$, $1\le k\le5$), la taille de la permutation et le nombre de couleurs.

La deuxième ligne de chaque cas contient $k+1$ entiers $S,C_1,C_2,\ldots,C_k$ ($0\le S,C_i\le10^9$), les coûts des opérations.

La troisième ligne de chaque cas contient $n$ entiers $p_1,p_2,\ldots,p_n$ ($1\le p_i\le n$, tous les $p_i$ sont distincts), la permutation.

La quatrième ligne de chaque cas contient $n$ entiers $col_i$ ($1\le col_i\le k$), les couleurs des positions.

La somme de $n$ sur tous les cas de test d'un fichier ne dépasse pas $10^5$.

Sortie

Pour chaque cas de test, affichez un entier : le nombre minimal de pièces à dépenser pour trier la permutation.

Exemples

Entrée 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

Sortie 1

3
1
12
0

Remarque

Dans le premier cas de test, nous pouvons trier la permutation en effectuant 3 échanges : $(2,3,4,1)\to(4,3,2,1)\to(4,2,3,1)\to(1,2,3,4)$. Vous dépenserez ainsi 3 pièces.

Une autre façon serait de permuter tous les éléments aux positions de couleur $1$, mais cela coûterait 10 pièces, et nous pouvons faire moins cher.

Dans le deuxième cas de test (qui ne diffère du premier que par les coûts des opérations), il est toutefois moins cher de simplement permuter tous les éléments aux positions de couleur $1$, en dépensant 1 pièce.

Dans le troisième cas de test, une suite optimale d'opérations serait la suivante :

• Permuter les éléments aux positions de couleur $2$ pour obtenir $(5,2,4,3,1,6)$. Cette opération coûte 1 pièce.
• Échanger les éléments $p_3,p_4$. La permutation est maintenant $(5,2,3,4,1,6)$. Cette opération coûte 10 pièces.
• Permuter les éléments aux positions de couleur $1$ pour obtenir $(1,2,3,4,5,6)$. Cette opération coûte 1 pièce.

Au total, nous avons dépensé 12 pièces.

Dans le quatrième cas de test, la permutation est déjà triée ; nous n'avons donc rien à dépenser.