$1$ から $n$ までの整数の順列 $p_1,p_2,\ldots,p_n$ が与えられます。$1$ から $n$ までの各位置は $k$ 色のいずれかで塗られています。この順列をソートするため、次の操作を任意の回数行うことができます。
- 任意の 2 つの要素を交換する。この操作には $S$ 枚のコインがかかります。
- 任意の色 $i$ を選び、その色の位置にある要素を好きなように並べ替える。この操作には $C_i$ 枚のコインがかかります。
色が付いているのは要素ではなく位置なので、2 つの要素を交換しても位置の色は変わりません。
順列をソートするために必要なコインの最小枚数を求めてください。
入力
最初の行には、処理する独立したテストケースの数を表す整数 $T$（$1\le T\le10^3$）が与えられます。続いて各テストケースの説明が与えられます。
各テストケースの最初の行には、順列の長さと色の数を表す整数 $n,k$（$1\le n\le10^5$, $1\le k\le5$）が与えられます。
2 行目には、操作の費用を表す $k+1$ 個の整数 $S,C_1,C_2,\ldots,C_k$（$0\le S,C_i\le10^9$）が与えられます。
3 行目には、順列を表す $n$ 個の整数 $p_1,p_2,\ldots,p_n$（$1\le p_i\le n$、すべての $p_i$ は異なる）が与えられます。
4 行目には、各位置の色を表す $n$ 個の整数 $col_i$（$1\le col_i\le k$）が与えられます。
1 つの入力ファイル内の全テストケースにわたる $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 枚のコインがかかり、もっと安くできます。
しかし、2 番目のテストケース（最初のケースとは操作の費用だけが異なります）では、色 $1$ の位置にあるすべての要素を並べ替え、コインを 1 枚使う方が安くなります。
3 番目のテストケースの最適な操作列の一つは次のとおりです。
- 色 $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 枚のコインを使いました。
4 番目のテストケースでは、順列はすでにソートされているので、コインを使う必要はありません。