Little Cyan Fish ha due strisce luminose, ciascuna contenente $n$ luci numerate da $1$ a $n$. Ogni luce è accesa oppure spenta. Gli stati iniziali delle due strisce sono descritti da stringhe binarie $a$ e $b$ di lunghezza $n$, dove 1 indica una luce accesa e 0 indica una luce spenta.

Ci sono $n + 1$ interfacce di controllo, numerate da $0$ a $n$. L'interfaccia $0$ si trova prima della prima luce, e l'interfaccia $i$ si trova immediatamente dopo la luce $i$ per ogni $1 \le i \le n$. L'interfaccia $i$ ha un parametro di costo $c_i$.

In un'operazione, Little Cyan Fish sceglie due interfacce $p$ e $q$ ($0 \le p < q \le n$) ed esegue una delle seguenti azioni:

• Invertire tutte le luci numerate $p + 1, p + 2, \dots, q$ sulla prima striscia;
• Invertire tutte le luci numerate $p + 1, p + 2, \dots, q$ sulla seconda striscia;
• Invertire tutte le luci numerate $p + 1, p + 2, \dots, q$ su entrambe le strisce.

Invertire una luce cambia il suo stato da accesa a spenta o da spenta a accesa. Ciascuna delle tre azioni costa $\max(c_p, c_q)$. Le interfacce possono essere utilizzate ripetutamente e non c'è limite al numero di operazioni.

Trova il costo totale minimo necessario per spegnere tutte le luci su entrambe le strisce.

Input

Ci sono più casi di test. La prima riga dell'input contiene un singolo intero $T$ ($1 \le T$), che indica il numero di casi di test.

Per ogni caso di test, la prima riga contiene un singolo intero $n$ ($1 \le n \le 3 \times 10^5$), che indica il numero di luci su ciascuna striscia.

La seconda e la terza riga contengono rispettivamente le stringhe binarie $a$ e $b$ di lunghezza $n$, composte solo dai caratteri 0 e 1.

La quarta riga contiene $n + 1$ interi $c_0, c_1, \dots, c_n$ ($1 \le c_i \le 10^9$), che indicano i parametri di costo delle interfacce.

È garantito che la somma di $n$ su tutti i casi di test non superi $3 \times 10^5$.

Output

Per ogni caso di test, stampa una singola riga contenente un singolo intero, che indica il costo totale minimo necessario per spegnere tutte le luci su entrambe le strisce.

Esempi

Input 1

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

Output 1

0
9
101

Nota

Nel primo caso di test di esempio, tutte le luci sono già spente, quindi non è necessaria alcuna operazione.

Nel secondo caso di test di esempio, Little Cyan Fish sceglie le interfacce $0$ e $1$ e inverte entrambe le luci. Questa operazione costa $\max(7, 9) = 9$.

Nel terzo caso di test di esempio, prima inverte tutte le luci sulla prima striscia usando le interfacce $0$ e $3$, al costo di $1$. Poi inverte la sua luce centrale usando le interfacce $1$ e $2$, al costo di $100$. Il costo totale è $101$.