Gegeben ist eine Permutation $p_1,p_2,\ldots,p_n$ der ganzen Zahlen von $1$ bis $n$. Jede Position von $1$ bis $n$ ist in einer von $k$ Farben gefärbt. Wir wollen die Permutation sortieren und dürfen dafür beliebig viele Operationen der folgenden Typen ausführen:

• Vertausche zwei beliebige Elemente. Diese Operation kostet $S$ Münzen;
• Wähle eine beliebige Farbe $i$ und ordne die Elemente auf Positionen der Farbe $i$ beliebig um. Diese Operation kostet $C_i$ Münzen.

Beachte, dass die Positionen gefärbt sind, nicht die Elemente. Beim Vertauschen zweier Elemente ändern die Positionen ihre Farben daher nicht.

Bestimme die minimale Anzahl an Münzen, die du zum Sortieren der Permutation ausgeben musst.

Eingabe

Die erste Zeile enthält eine ganze Zahl $T$ ($1\le T\le10^3$), die Anzahl der unabhängigen Testfälle, die du verarbeiten musst. Es folgen die Beschreibungen der Testfälle.

Die erste Zeile jedes Testfalls enthält zwei ganze Zahlen $n,k$ ($1\le n\le10^5$, $1\le k\le5$), die Größe der Permutation und die Anzahl der Farben.

Die zweite Zeile jedes Testfalls enthält $k+1$ ganze Zahlen $S,C_1,C_2,\ldots,C_k$ ($0\le S,C_i\le10^9$), die Kosten der Operationen.

Die dritte Zeile jedes Testfalls enthält $n$ ganze Zahlen $p_1,p_2,\ldots,p_n$ ($1\le p_i\le n$, alle $p_i$ sind verschieden), die Permutation.

Die vierte Zeile jedes Testfalls enthält $n$ ganze Zahlen $col_i$ ($1\le col_i\le k$), die Farben der Positionen.

Die Summe von $n$ über alle Testfälle einer Datei überschreitet $10^5$ nicht.

Ausgabe

Gib für jeden Testfall eine ganze Zahl aus: die minimale Anzahl an Münzen, die du zum Sortieren der Permutation ausgeben musst.

Beispiele

Eingabe 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

Ausgabe 1

3
1
12
0

Hinweis

Im ersten Testfall können wir die Permutation mit 3 Vertauschungen sortieren: $(2,3,4,1)\to(4,3,2,1)\to(4,2,3,1)\to(1,2,3,4)$. Dabei werden 3 Münzen ausgegeben.

Eine andere Möglichkeit wäre, alle Elemente auf Positionen der Farbe $1$ umzuordnen. Das würde aber 10 Münzen kosten, und es geht günstiger.

Im zweiten Testfall (der sich vom ersten nur durch die Operationskosten unterscheidet) ist es dagegen günstiger, einfach alle Elemente auf Positionen der Farbe $1$ umzuordnen und dafür 1 Münze auszugeben.

Im dritten Testfall ist eine optimale Operationsfolge:

• Ordne die Elemente auf Positionen der Farbe $2$ um, um $(5,2,4,3,1,6)$ zu erhalten. Diese Operation kostet 1 Münze.
• Vertausche die Elemente $p_3,p_4$. Die Permutation lautet nun $(5,2,3,4,1,6)$. Diese Operation kostet 10 Münzen.
• Ordne die Elemente auf Positionen der Farbe $1$ um, um $(1,2,3,4,5,6)$ zu erhalten. Diese Operation kostet 1 Münze.

Insgesamt wurden 12 Münzen ausgegeben.

Im vierten Testfall ist die Permutation bereits sortiert, sodass wir nichts ausgeben müssen.