Дана перестановка $p_1,p_2,\ldots,p_n$ целых чисел от $1$ до $n$. Каждая позиция от $1$ до $n$ окрашена в один из $k$ цветов. Мы хотим отсортировать перестановку и для этого можем выполнить любое количество операций следующих типов:

• Поменять местами любые два элемента. Эта операция стоит $S$ монет;
• Выбрать любой цвет $i$ и произвольным образом переставить элементы на позициях цвета $i$. Эта операция стоит $C_i$ монет.

Обратите внимание, что окрашены позиции, а не элементы, поэтому при обмене двух элементов цвета позиций не меняются.

Найдите минимальное количество монет, которое нужно потратить, чтобы отсортировать перестановку.

Входные данные

Первая строка содержит одно целое число $T$ ($1\le T\le10^3$) — количество независимых тестовых случаев, которые нужно обработать. Далее следуют их описания.

Первая строка каждого случая содержит два целых числа $n,k$ ($1\le n\le10^5$, $1\le k\le5$) — размер перестановки и количество цветов.

Вторая строка каждого случая содержит $k+1$ целых чисел $S,C_1,C_2,\ldots,C_k$ ($0\le S,C_i\le10^9$) — стоимости операций.

Третья строка каждого случая содержит $n$ целых чисел $p_1,p_2,\ldots,p_n$ ($1\le p_i\le n$, все $p_i$ различны) — перестановку.

Четвёртая строка каждого случая содержит $n$ целых чисел $col_i$ ($1\le col_i\le k$) — цвета позиций.

Сумма $n$ по всем тестовым случаям одного файла не превышает $10^5$.

Выходные данные

Для каждого тестового случая выведите одно целое число — минимальное количество монет, которое нужно потратить, чтобы отсортировать перестановку.

Примеры

Входные данные 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

Выходные данные 1

3
1
12
0

Примечание

В первом тестовом случае можно отсортировать перестановку, выполнив операцию обмена 3 раза: $(2,3,4,1)\to(4,3,2,1)\to(4,2,3,1)\to(1,2,3,4)$. Таким образом вы потратите 3 монеты.

Другой способ — переставить все элементы на позициях цвета $1$, но это стоило бы 10 монет, а можно сделать дешевле.

Однако во втором тестовом случае (который отличается от первого только стоимостями операций) дешевле просто переставить все элементы на позициях цвета $1$, потратив 1 монету.

В третьем тестовом случае одна из оптимальных последовательностей операций такова:

• Переставить элементы на позициях цвета $2$, получив перестановку $(5,2,4,3,1,6)$. Эта операция стоит 1 монету.
• Поменять местами элементы $p_3,p_4$. Теперь перестановка имеет вид $(5,2,3,4,1,6)$. Эта операция стоит 10 монет.
• Переставить элементы на позициях цвета $1$, получив перестановку $(1,2,3,4,5,6)$. Эта операция стоит 1 монету.

Всего мы потратили 12 монет.

В четвёртом тестовом случае перестановка уже отсортирована, поэтому ничего тратить не нужно.