Little Cyan Fish は 2 本のライトストリップを持っており、それぞれには $n$ 個のライトが含まれ、$1$ から $n$ までの番号が付けられています。各ライトは点灯（on）または消灯（off）のいずれかの状態です。2 本のストリップの初期状態は長さ $n$ の 2 進文字列 $a$ と $b$ によって表され、ここで 1 は点灯しているライトを、0 は消灯しているライトを表します。

$n + 1$ 個の制御インターフェースがあり、$0$ から $n$ までの番号が付けられています。インターフェース $0$ は最初のライトの前にあり、各 $1 \le i \le n$ についてインターフェース $i$ はライト $i$ の直後にあります。インターフェース $i$ はコストパラメータ $c_i$ を持っています。

1 回の操作で、Little Cyan Fish は 2 つのインターフェース $p$ と $q$（$0 \le p < q \le n$）を選び、次のいずれかの動作を行います：

• 1 本目のストリップの番号 $p + 1, p + 2, \dots, q$ のすべてのライトの状態を反転させる；
• 2 本目のストリップの番号 $p + 1, p + 2, \dots, q$ のすべてのライトの状態を反転させる；
• 両方のストリップの番号 $p + 1, p + 2, \dots, q$ のすべてのライトの状態を反転させる。

ライトの状態を反転させるとは、点灯から消灯へ、または消灯から点灯へと状態を変えることです。これら 3 つの動作はいずれも $\max(c_p, c_q)$ のコストがかかります。インターフェースは繰り返し使用でき、操作の回数に制限はありません。

両方のストリップのすべてのライトを消灯させるために必要な最小の合計コストを求めてください。

入力

複数のテストケースが与えられます。入力の 1 行目には、テストケースの個数を表す 1 つの整数 $T$（$1 \le T$）が含まれます。

各テストケースについて、1 行目には各ストリップのライトの個数を表す 1 つの整数 $n$（$1 \le n \le 3 \times 10^5$）が含まれます。

2 行目と 3 行目には、それぞれ文字 0 と 1 のみからなる長さ $n$ の 2 進文字列 $a$ と $b$ が含まれます。

4 行目には、インターフェースのコストパラメータを表す $n + 1$ 個の整数 $c_0, c_1, \dots, c_n$（$1 \le c_i \le 10^9$）が含まれます。

すべてのテストケースにおける $n$ の総和は $3 \times 10^5$ を超えないことが保証されています。

出力

各テストケースについて、両方のストリップのすべてのライトを消灯させるために必要な最小の合計コストを表す 1 つの整数を 1 行に出力してください。

入出力例

入力 1

3
1
0
0
1 1
1
1
1
7 9
3
101
000
1 100 100 1

出力 1

0
9
101

注記

1 番目のサンプルテストケースでは、すべてのライトがすでに消灯しているため、操作は必要ありません。

2 番目のサンプルテストケースでは、Little Cyan Fish はインターフェース $0$ と $1$ を選び、両方のライトを反転させます。この操作のコストは $\max(7, 9) = 9$ です。

3 番目のサンプルテストケースでは、彼はまずインターフェース $0$ と $3$ を使って 1 本目のストリップのすべてのライトをコスト $1$ で反転させます。次にインターフェース $1$ と $2$ を使ってその中央のライトをコスト $100$ で反転させます。合計コストは $101$ です。