Dana jest permutacja $p_1,p_2,\ldots,p_n$ liczb całkowitych od $1$ do $n$. Każda pozycja od $1$ do $n$ jest pomalowana na jeden z $k$ kolorów. Chcemy posortować permutację i możemy w tym celu wykonać dowolną liczbę operacji następujących typów:

• Zamienić miejscami dowolne dwa elementy. Ta operacja kosztuje $S$ monet;
• Wybrać dowolny kolor $i$ i dowolnie przestawić elementy na pozycjach koloru $i$. Ta operacja kosztuje $C_i$ monet.

Zauważ, że pokolorowane są pozycje, a nie elementy, więc zamiana dwóch elementów nie zmienia kolorów pozycji.

Znajdź minimalną liczbę monet potrzebną do posortowania permutacji.

Wejście

Pierwszy wiersz zawiera jedną liczbę całkowitą $T$ ($1\le T\le10^3$) — liczbę niezależnych przypadków testowych do przetworzenia. Dalej podano ich opisy.

Pierwszy wiersz każdego przypadku zawiera dwie liczby całkowite $n,k$ ($1\le n\le10^5$, $1\le k\le5$) — rozmiar permutacji i liczbę kolorów.

Drugi wiersz każdego przypadku zawiera $k+1$ liczb całkowitych $S,C_1,C_2,\ldots,C_k$ ($0\le S,C_i\le10^9$) — koszty operacji.

Trzeci wiersz każdego przypadku zawiera $n$ liczb całkowitych $p_1,p_2,\ldots,p_n$ ($1\le p_i\le n$, wszystkie $p_i$ są różne) — permutację.

Czwarty wiersz każdego przypadku zawiera $n$ liczb całkowitych $col_i$ ($1\le col_i\le k$) — kolory pozycji.

Suma $n$ po wszystkich przypadkach testowych w jednym pliku nie przekracza $10^5$.

Wyjście

Dla każdego przypadku testowego wypisz jedną liczbę całkowitą — minimalną liczbę monet potrzebną do posortowania permutacji.

Przykład

Wejście 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

Wyjście 1

3
1
12
0

Uwagi

W pierwszym przypadku testowym możemy posortować permutację, wykonując operację zamiany 3 razy: $(2,3,4,1)\to(4,3,2,1)\to(4,2,3,1)\to(1,2,3,4)$. W ten sposób wydamy 3 monety.

Innym sposobem byłoby przestawienie wszystkich elementów na pozycjach koloru $1$, ale kosztowałoby to 10 monet, a można zrobić to taniej.

W drugim przypadku testowym (który różni się od pierwszego tylko kosztami operacji) taniej jest jednak po prostu przestawić wszystkie elementy na pozycjach koloru $1$, wydając 1 monetę.

W trzecim przypadku testowym jednym z optymalnych ciągów operacji jest:

• Przestawienie elementów na pozycjach koloru $2$, aby otrzymać permutację $(5,2,4,3,1,6)$. Ta operacja kosztuje 1 monetę.
• Zamiana elementów $p_3,p_4$. Permutacja ma teraz postać $(5,2,3,4,1,6)$. Ta operacja kosztuje 10 monet.
• Przestawienie elementów na pozycjach koloru $1$, aby otrzymać permutację $(1,2,3,4,5,6)$. Ta operacja kosztuje 1 monetę.

Łącznie wydaliśmy 12 monet.

W czwartym przypadku testowym permutacja jest już posortowana, więc nie musimy nic wydawać.