Дано перестановку $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 монет.

У четвертому тестовому випадку перестановка вже відсортована, тому нічого витрачати не потрібно.