Little Cyan Fish possède deux rubans lumineux, chacun contenant $n$ lampes numérotées de $1$ à $n$. Chaque lampe est soit allumée, soit éteinte. Les états initiaux des deux rubans sont décrits par des chaînes binaires $a$ et $b$ de longueur $n$, où 1 désigne une lampe allumée et 0 désigne une lampe éteinte.

Il y a $n + 1$ interfaces de contrôle, numérotées de $0$ à $n$. L'interface $0$ se trouve avant la première lampe, et l'interface $i$ se trouve immédiatement après la lampe $i$ pour chaque $1 \le i \le n$. L'interface $i$ possède un paramètre de coût $c_i$.

En une opération, Little Cyan Fish choisit deux interfaces $p$ et $q$ ($0 \le p < q \le n$) et effectue l'une des actions suivantes :

• Inverser toutes les lampes numérotées $p + 1, p + 2, \dots, q$ sur le premier ruban ;
• Inverser toutes les lampes numérotées $p + 1, p + 2, \dots, q$ sur le second ruban ;
• Inverser toutes les lampes numérotées $p + 1, p + 2, \dots, q$ sur les deux rubans.

Inverser une lampe change son état d'allumée à éteinte ou d'éteinte à allumée. Chacune des trois actions coûte $\max(c_p, c_q)$. Les interfaces peuvent être utilisées de manière répétée, et il n'y a aucune limite sur le nombre d'opérations.

Trouvez le coût total minimal nécessaire pour éteindre toutes les lampes sur les deux rubans.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un seul entier $T$ ($1 \le T$), indiquant le nombre de cas de test.

Pour chaque cas de test, la première ligne contient un seul entier $n$ ($1 \le n \le 3 \times 10^5$), indiquant le nombre de lampes sur chaque ruban.

Les deuxième et troisième lignes contiennent respectivement les chaînes binaires $a$ et $b$ de longueur $n$, composées uniquement des caractères 0 et 1.

La quatrième ligne contient $n + 1$ entiers $c_0, c_1, \dots, c_n$ ($1 \le c_i \le 10^9$), indiquant les paramètres de coût des interfaces.

Il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $3 \times 10^5$.

Sortie

Pour chaque cas de test, affichez une seule ligne contenant un seul entier, indiquant le coût total minimal nécessaire pour éteindre toutes les lampes sur les deux rubans.

Exemples

Entrée 1

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

Sortie 1

0
9
101

Remarque

Dans le premier cas de test de l'exemple, toutes les lampes sont déjà éteintes, donc aucune opération n'est nécessaire.

Dans le deuxième cas de test de l'exemple, Little Cyan Fish choisit les interfaces $0$ et $1$ et inverse les deux lampes. Cette opération coûte $\max(7, 9) = 9$.

Dans le troisième cas de test de l'exemple, il inverse d'abord toutes les lampes du premier ruban en utilisant les interfaces $0$ et $3$, pour un coût de $1$. Il inverse ensuite sa lampe du milieu en utilisant les interfaces $1$ et $2$, pour un coût de $100$. Le coût total est de $101$.