Diberikan permutasi $p_1,p_2,\ldots,p_n$ dari bilangan bulat $1$ hingga $n$. Setiap posisi dari $1$ hingga $n$ diwarnai dengan salah satu dari $k$ warna. Kita ingin mengurutkan permutasi tersebut, dan untuk itu kita dapat melakukan operasi berikut berapa kali pun:

• Menukar sembarang dua elemen. Operasi ini membutuhkan $S$ koin;
• Memilih sembarang warna $i$, lalu menyusun ulang elemen pada posisi berwarna $i$ sesuka hati. Operasi ini membutuhkan $C_i$ koin.

Perhatikan bahwa yang diwarnai adalah posisi, bukan elemen, sehingga ketika dua elemen ditukar, warna posisi tidak berubah.

Carilah jumlah koin minimum yang perlu dikeluarkan untuk mengurutkan permutasi.

Masukan

Baris pertama berisi sebuah bilangan bulat $T$ ($1\le T\le10^3$), yaitu jumlah kasus uji independen yang perlu diproses. Deskripsi kasus-kasus uji menyusul.

Baris pertama setiap kasus uji berisi dua bilangan bulat $n,k$ ($1\le n\le10^5$, $1\le k\le5$), yaitu ukuran permutasi dan jumlah warna.

Baris kedua setiap kasus uji berisi $k+1$ bilangan bulat $S,C_1,C_2,\ldots,C_k$ ($0\le S,C_i\le10^9$), yaitu biaya operasi.

Baris ketiga setiap kasus uji berisi $n$ bilangan bulat $p_1,p_2,\ldots,p_n$ ($1\le p_i\le n$, semua $p_i$ berbeda), yaitu permutasi.

Baris keempat setiap kasus uji berisi $n$ bilangan bulat $col_i$ ($1\le col_i\le k$), yaitu warna posisi.

Jumlah $n$ untuk semua kasus uji dalam satu berkas tidak melebihi $10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan sebuah bilangan bulat, yaitu jumlah koin minimum yang perlu dikeluarkan untuk mengurutkan permutasi.

Contoh

Masukan 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

Keluaran 1

3
1
12
0

Catatan

Pada kasus uji pertama, kita dapat mengurutkan permutasi dengan melakukan operasi penukaran 3 kali: $(2,3,4,1)\to(4,3,2,1)\to(4,2,3,1)\to(1,2,3,4)$. Dengan cara ini Anda mengeluarkan 3 koin.

Cara lain adalah menyusun ulang semua elemen pada posisi berwarna $1$, tetapi ini membutuhkan 10 koin, dan kita dapat melakukannya dengan lebih murah.

Namun, pada kasus uji kedua (yang hanya berbeda dari kasus pertama dalam biaya operasi), lebih murah untuk langsung menyusun ulang semua elemen pada posisi berwarna $1$ dengan mengeluarkan 1 koin.

Pada kasus uji ketiga, salah satu urutan operasi optimal adalah sebagai berikut:

• Susun ulang elemen pada posisi berwarna $2$ untuk mendapatkan permutasi $(5,2,4,3,1,6)$. Operasi ini membutuhkan 1 koin.
• Tukar elemen $p_3,p_4$. Permutasi sekarang menjadi $(5,2,3,4,1,6)$. Operasi ini membutuhkan 10 koin.
• Susun ulang elemen pada posisi berwarna $1$ untuk mendapatkan permutasi $(1,2,3,4,5,6)$. Operasi ini membutuhkan 1 koin.

Secara keseluruhan, kita mengeluarkan 12 koin.

Pada kasus uji keempat, permutasi sudah terurut, sehingga kita tidak perlu mengeluarkan apa pun.