Little Cyan Fish tiene dos tiras de luces, cada una con $n$ luces etiquetadas de $1$ a $n$. Cada luz está encendida o apagada. Los estados iniciales de las dos tiras se describen mediante cadenas binarias $a$ y $b$ de longitud $n$, donde 1 denota una luz encendida y 0 denota una luz apagada.

Hay $n + 1$ interfaces de control, etiquetadas de $0$ a $n$. La interfaz $0$ está antes de la primera luz, y la interfaz $i$ está inmediatamente después de la luz $i$ para cada $1 \le i \le n$. La interfaz $i$ tiene un parámetro de costo $c_i$.

En una operación, Little Cyan Fish elige dos interfaces $p$ y $q$ ($0 \le p < q \le n$) y realiza una de las siguientes acciones:

• Invertir todas las luces etiquetadas $p + 1, p + 2, \dots, q$ en la primera tira;
• Invertir todas las luces etiquetadas $p + 1, p + 2, \dots, q$ en la segunda tira;
• Invertir todas las luces etiquetadas $p + 1, p + 2, \dots, q$ en ambas tiras.

Invertir una luz cambia su estado de encendida a apagada o de apagada a encendida. Cada una de las tres acciones cuesta $\max(c_p, c_q)$. Las interfaces pueden utilizarse repetidamente y no hay límite en el número de operaciones.

Halla el costo total mínimo necesario para apagar todas las luces en ambas tiras.

Entrada

Hay múltiples casos de prueba. La primera línea de la entrada contiene un solo entero $T$ ($1 \le T$), que indica el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene un solo entero $n$ ($1 \le n \le 3 \times 10^5$), que indica el número de luces en cada tira.

La segunda y la tercera línea contienen las cadenas binarias $a$ y $b$ de longitud $n$, respectivamente, compuestas únicamente por los caracteres 0 y 1.

La cuarta línea contiene $n + 1$ enteros $c_0, c_1, \dots, c_n$ ($1 \le c_i \le 10^9$), que indican los parámetros de costo de las interfaces.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $3 \times 10^5$.

Salida

Para cada caso de prueba, imprime una sola línea que contenga un solo entero, indicando el costo total mínimo necesario para apagar todas las luces en ambas tiras.

Ejemplos

Entrada 1

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

Salida 1

0
9
101

Nota

En el primer caso de prueba de ejemplo, todas las luces ya están apagadas, por lo que no se necesita ninguna operación.

En el segundo caso de prueba de ejemplo, Little Cyan Fish elige las interfaces $0$ y $1$ e invierte ambas luces. Esta operación cuesta $\max(7, 9) = 9$.

En el tercer caso de prueba de ejemplo, primero invierte todas las luces de la primera tira usando las interfaces $0$ y $3$, con un costo de $1$. Luego invierte su luz central usando las interfaces $1$ y $2$, con un costo de $100$. El costo total es $101$.