Bạn được cho một hoán vị $p_1,p_2,\ldots,p_n$ của các số nguyên từ $1$ đến $n$. Mỗi vị trí từ $1$ đến $n$ được tô một trong $k$ màu. Ta muốn sắp xếp hoán vị và có thể thực hiện tùy ý số lần các thao tác sau:

• Đổi chỗ hai phần tử bất kỳ. Thao tác này tốn $S$ đồng xu;
• Chọn một màu $i$ bất kỳ và hoán đổi tùy ý thứ tự các phần tử tại những vị trí có màu $i$. Thao tác này tốn $C_i$ đồng xu.

Lưu ý rằng các vị trí được tô màu, chứ không phải các phần tử, nên khi đổi chỗ hai phần tử, màu của các vị trí không thay đổi.

Tìm số đồng xu ít nhất cần chi để sắp xếp hoán vị.

Dữ liệu vào

Dòng đầu chứa một số nguyên $T$ ($1\le T\le10^3$), là số bộ kiểm thử độc lập cần xử lý. Tiếp theo là mô tả các bộ kiểm thử.

Dòng đầu của mỗi bộ kiểm thử chứa hai số nguyên $n,k$ ($1\le n\le10^5$, $1\le k\le5$), là kích thước hoán vị và số màu.

Dòng thứ hai của mỗi bộ kiểm thử chứa $k+1$ số nguyên $S,C_1,C_2,\ldots,C_k$ ($0\le S,C_i\le10^9$), là chi phí các thao tác.

Dòng thứ ba của mỗi bộ kiểm thử chứa $n$ số nguyên $p_1,p_2,\ldots,p_n$ ($1\le p_i\le n$, mọi $p_i$ đều khác nhau), là hoán vị.

Dòng thứ tư của mỗi bộ kiểm thử chứa $n$ số nguyên $col_i$ ($1\le col_i\le k$), là màu của các vị trí.

Tổng $n$ trên mọi bộ kiểm thử trong một tệp không vượt quá $10^5$.

Dữ liệu ra

Với mỗi bộ kiểm thử, in một số nguyên là số đồng xu ít nhất cần chi để sắp xếp hoán vị.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

3
1
12
0

Ghi chú

Trong bộ kiểm thử thứ nhất, ta có thể sắp xếp hoán vị bằng cách thực hiện thao tác đổi chỗ 3 lần: $(2,3,4,1)\to(4,3,2,1)\to(4,2,3,1)\to(1,2,3,4)$. Cách này tốn 3 đồng xu.

Một cách khác là hoán đổi thứ tự tất cả các phần tử tại những vị trí màu $1$, nhưng cách đó tốn 10 đồng xu, trong khi ta có thể làm rẻ hơn.

Tuy nhiên, ở bộ kiểm thử thứ hai (chỉ khác bộ thứ nhất ở chi phí thao tác), chỉ cần hoán đổi thứ tự tất cả các phần tử tại những vị trí màu $1$ sẽ rẻ hơn, tốn 1 đồng xu.

Trong bộ kiểm thử thứ ba, một dãy thao tác tối ưu như sau:

• Hoán đổi thứ tự các phần tử tại những vị trí màu $2$ để thu được hoán vị $(5,2,4,3,1,6)$. Thao tác này tốn 1 đồng xu.
• Đổi chỗ các phần tử $p_3,p_4$. Hoán vị lúc này là $(5,2,3,4,1,6)$. Thao tác này tốn 10 đồng xu.
• Hoán đổi thứ tự các phần tử tại những vị trí màu $1$ để thu được hoán vị $(1,2,3,4,5,6)$. Thao tác này tốn 1 đồng xu.

Tổng cộng ta đã chi 12 đồng xu.

Trong bộ kiểm thử thứ tư, hoán vị đã được sắp xếp nên không cần chi gì cả.