小青鱼有两条灯带，每条灯带包含 $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$。