小青魚有兩條燈帶，每條燈帶都有 $n$ 盞燈，由 $1$ 到 $n$ 編號。每盞燈一係着緊，一係熄咗。兩條燈帶嘅初始狀態由兩個長度係 $n$ 嘅二進制字串 $a$ 同 $b$ 描述，其中 1 代表着緊嘅燈，0 代表熄咗嘅燈。

總共有 $n + 1$ 個控制接口，由 $0$ 到 $n$ 編號。接口 $0$ 喺第一盞燈之前，而對於每個 $1 \le i \le n$，接口 $i$ 緊貼喺第 $i$ 盞燈之後。接口 $i$ 有一個成本參數 $c_i$。

喺一次操作入面，小青魚會揀兩個接口 $p$ 同 $q$（$0 \le p < q \le n$），然後執行以下其中一個動作：

• 將第一條燈帶上面編號係 $p + 1, p + 2, \dots, q$ 嘅所有燈反轉狀態；
• 將第二條燈帶上面編號係 $p + 1, p + 2, \dots, q$ 嘅所有燈反轉狀態；
• 將兩條燈帶上面編號係 $p + 1, p + 2, \dots, q$ 嘅所有燈一齊反轉狀態。

反轉一盞燈嘅狀態會將佢由着變熄，或者由熄變着。以上三個動作嘅成本都係 $\max(c_p, c_q)$。接口可以重複使用，而且操作次數冇限制。

請搵出將兩條燈帶上面所有燈全部熄晒所需嘅最小總成本。

輸入格式

呢道題有多組測試數據。輸入嘅第一行包含一個整數 $T$（$1 \le T$），代表測試數據嘅組數。

對於每組測試數據，第一行包含一個整數 $n$（$1 \le n \le 3 \times 10^5$），代表每條燈帶上面燈嘅數量。

第二行同第三行分別包含長度係 $n$ 嘅二進制字串 $a$ 同 $b$，淨係由字符 0 同 1 組成。

第四行包含 $n + 1$ 個整數 $c_0, c_1, \dots, c_n$（$1 \le c_i \le 10^9$），代表各個接口嘅成本參數。

題目保證所有測試數據入面 $n$ 嘅總和唔超過 $3 \times 10^5$。

輸出格式

對於每組測試數據，輸出一行包含一個整數，代表將兩條燈帶上面所有燈全部熄晒所需嘅最小總成本。

範例

輸入 1

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

輸出 1

0
9
101

說明

喺第一組範例測試數據入面，所有燈本身已經熄晒，所以唔需要做任何操作。

喺第二組範例測試數據入面，小青魚揀接口 $0$ 同 $1$，將兩盞燈一齊反轉狀態。呢次操作嘅成本係 $\max(7, 9) = 9$。

喺第三組範例測試數據入面，佢首先用接口 $0$ 同 $3$ 將第一條燈帶上面嘅所有燈反轉狀態，成本係 $1$。跟住佢再用接口 $1$ 同 $2$ 將嗰條燈帶中間嗰盞燈反轉狀態，成本係 $100$。總成本係 $101$。