Little Cyan Fish har to lysremser som hver inneholder $n$ lys nummerert fra $1$ til $n$. Hvert lys er enten på eller av. Starttilstandene til de to remsene beskrives av binære strenger $a$ og $b$ med lengde $n$, der 1 betyr et påslått lys og 0 betyr et avslått lys.

Det finnes $n + 1$ kontrollgrensesnitt, nummerert fra $0$ til $n$. Grensesnitt $0$ er før det første lyset, og grensesnitt $i$ er rett etter lys $i$ for hver $1 \le i \le n$. Grensesnitt $i$ har en kostnadsparameter $c_i$.

I én operasjon velger Little Cyan Fish to grensesnitt $p$ og $q$ ($0 \le p < q \le n$) og utfører én av følgende handlinger:

• Veksle alle lys nummerert $p + 1, p + 2, \dots, q$ på den første remsen;
• Veksle alle lys nummerert $p + 1, p + 2, \dots, q$ på den andre remsen;
• Veksle alle lys nummerert $p + 1, p + 2, \dots, q$ på begge remsene.

Å veksle et lys endrer tilstanden fra på til av eller fra av til på. Hver av de tre handlingene koster $\max(c_p, c_q)$. Grensesnitt kan brukes gjentatte ganger, og det er ingen grense for antall operasjoner.

Finn den minste totale kostnaden som trengs for å slå av alle lysene på begge remsene.

Inndata

Det er flere testtilfeller. Den første linjen i inndataene inneholder et enkelt heltall $T$ ($1 \le T$), som angir antall testtilfeller.

For hvert testtilfelle inneholder den første linjen et enkelt heltall $n$ ($1 \le n \le 3 \times 10^5$), som angir antall lys på hver remse.

Den andre og tredje linjen inneholder de binære strengene henholdsvis $a$ og $b$ med lengde $n$, som kun består av tegnene 0 og 1.

Den fjerde linjen inneholder $n + 1$ heltall $c_0, c_1, \dots, c_n$ ($1 \le c_i \le 10^9$), som angir kostnadsparameterne til grensesnittene.

Det garanteres at summen av $n$ over alle testtilfeller ikke overstiger $3 \times 10^5$.

Utdata

For hvert testtilfelle, skriv ut en enkelt linje som inneholder et enkelt heltall, som angir den minste totale kostnaden som trengs for å slå av alle lysene på begge remsene.

Eksempler

Inndata 1

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

Utdata 1

0
9
101

Merk

I det første eksempeltesttilfellet er alle lysene allerede av, så ingen operasjon er nødvendig.

I det andre eksempeltesttilfellet velger Little Cyan Fish grensesnittene $0$ og $1$ og veksler begge lysene. Denne operasjonen koster $\max(7, 9) = 9$.

I det tredje eksempeltesttilfellet veksler han først alle lysene på den første remsen ved hjelp av grensesnittene $0$ og $3$, til kostnad $1$. Deretter veksler han det midterste lyset på den ved hjelp av grensesnittene $1$ og $2$, til kostnad $100$. Den totale kostnaden er $101$.