Little Cyan Fish á tvær ljósaræmur og á hvorri þeirra eru $n$ ljós merkt frá $1$ til $n$. Hvert ljós er annaðhvort kveikt eða slökkt. Upphafsstöður ræmanna tveggja eru lýstar með tvíundarstrengjum $a$ og $b$ af lengd $n$, þar sem 1 táknar kveikt ljós og 0 táknar slökkt ljós.

Það eru $n + 1$ stýriviðmót, merkt frá $0$ til $n$. Viðmót $0$ er fyrir framan fyrsta ljósið og viðmót $i$ er strax á eftir ljósi $i$ fyrir hvert $1 \le i \le n$. Viðmót $i$ hefur kostnaðarstika $c_i$.

Í einni aðgerð velur Little Cyan Fish tvö viðmót $p$ og $q$ ($0 \le p < q \le n$) og framkvæmir eina af eftirfarandi aðgerðum:

• Víxla stöðu allra ljósa sem eru merkt $p + 1, p + 2, \dots, q$ á fyrri ræmunni;
• Víxla stöðu allra ljósa sem eru merkt $p + 1, p + 2, \dots, q$ á seinni ræmunni;
• Víxla stöðu allra ljósa sem eru merkt $p + 1, p + 2, \dots, q$ á báðum ræmunum.

Að víxla stöðu ljóss breytir stöðu þess úr kveiktu í slökkt eða úr slökktu í kveikt. Hver af þessum þremur aðgerðum kostar $\max(c_p, c_q)$. Nota má viðmótin endurtekið og engin takmörk eru á fjölda aðgerða.

Finndu lágmarks heildarkostnað sem þarf til að slökkva á öllum ljósum á báðum ræmunum.

Inntak

Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur eina heiltölu $T$ ($1 \le T$), sem gefur til kynna fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan eina heiltölu $n$ ($1 \le n \le 3 \times 10^5$), sem gefur til kynna fjölda ljósa á hvorri ræmu.

Önnur og þriðja línan innihalda tvíundarstrengina $a$ og $b$ af lengd $n$, í þessari röð, sem samanstanda eingöngu af stöfunum 0 og 1.

Fjórða línan inniheldur $n + 1$ heiltölur $c_0, c_1, \dots, c_n$ ($1 \le c_i \le 10^9$), sem gefa til kynna kostnaðarstika viðmótanna.

Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $3 \times 10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur eina heiltölu, sem gefur til kynna lágmarks heildarkostnað sem þarf til að slökkva á öllum ljósum á báðum ræmunum.

Dæmi

Inntak 1

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

Úttak 1

0
9
101

Athugasemd

Í fyrsta prófunartilvikinu í dæminu er þegar slökkt á öllum ljósum, svo engin aðgerð er nauðsynleg.

Í öðru prófunartilvikinu í dæminu velur Little Cyan Fish viðmótin $0$ og $1$ og víxlar stöðu beggja ljósanna. Þessi aðgerð kostar $\max(7, 9) = 9$.

Í þriðja prófunartilvikinu í dæminu víxlar hann fyrst stöðu allra ljósa á fyrri ræmunni með því að nota viðmótin $0$ og $3$, með kostnaðinum $1$. Síðan víxlar hann stöðu miðjuljóssins á henni með því að nota viðmótin $1$ og $2$, með kostnaðinum $100$. Heildarkostnaðurinn er $101$.