小青魚有兩條燈帶，每條燈帶包含 $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$。