Little Cyan Fishillä on kaksi valonauhaa, joista kumpikin sisältää $n$ valoa, jotka on numeroitu $1$:stä $n$:ään. Jokainen valo on joko päällä tai pois päältä. Kahden nauhan alkutilat kuvataan binäärijonoilla $a$ ja $b$, joiden pituus on $n$, missä 1 tarkoittaa päällä olevaa valoa ja 0 tarkoittaa pois päältä olevaa valoa.

On olemassa $n + 1$ ohjausliitäntää, jotka on numeroitu $0$:sta $n$:ään. Liitäntä $0$ on ennen ensimmäistä valoa, ja liitäntä $i$ on välittömästi valon $i$ jälkeen jokaisella $1 \le i \le n$. Liitännällä $i$ on kustannusparametri $c_i$.

Yhdellä operaatiolla Little Cyan Fish valitsee kaksi liitäntää $p$ ja $q$ ($0 \le p < q \le n$) ja suorittaa yhden seuraavista toiminnoista:

• Käännä kaikkien valojen $p + 1, p + 2, \dots, q$ tila ensimmäisessä nauhassa;
• Käännä kaikkien valojen $p + 1, p + 2, \dots, q$ tila toisessa nauhassa;
• Käännä kaikkien valojen $p + 1, p + 2, \dots, q$ tila molemmissa nauhoissa.

Valon tilan kääntäminen muuttaa sen tilan päältä pois päältä tai pois päältä päälle. Jokainen kolmesta toiminnosta maksaa $\max(c_p, c_q)$. Liitäntöjä voi käyttää toistuvasti, eikä operaatioiden määrää ole rajoitettu.

Etsi pienin kokonaiskustannus, joka tarvitaan kaikkien valojen sammuttamiseen molemmissa nauhoissa.

Syöte

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $T$ ($1 \le T$), joka ilmaisee testitapausten lukumäärän.

Jokaisessa testitapauksessa ensimmäinen rivi sisältää yhden kokonaisluvun $n$ ($1 \le n \le 3 \times 10^5$), joka ilmaisee valojen lukumäärän kummassakin nauhassa.

Toinen ja kolmas rivi sisältävät pituutta $n$ olevat binäärijonot $a$ ja $b$ tässä järjestyksessä, ja ne koostuvat vain merkeistä 0 ja 1.

Neljäs rivi sisältää $n + 1$ kokonaislukua $c_0, c_1, \dots, c_n$ ($1 \le c_i \le 10^9$), jotka ilmaisevat liitäntöjen kustannusparametrit.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $3 \times 10^5$.

Tuloste

Tulosta jokaista testitapausta kohden yksi rivi, joka sisältää yhden kokonaisluvun: pienimmän kokonaiskustannuksen, joka tarvitaan kaikkien valojen sammuttamiseen molemmissa nauhoissa.

Esimerkit

Syöte 1

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

Tuloste 1

0
9
101

Huomautus

Ensimmäisessä esimerkkitestitapauksessa kaikki valot ovat jo valmiiksi pois päältä, joten yhtäkään operaatiota ei tarvita.

Toisessa esimerkkitestitapauksessa Little Cyan Fish valitsee liitännät $0$ ja $1$ ja kääntää molempien valojen tilan. Tämä operaatio maksaa $\max(7, 9) = 9$.

Kolmannessa esimerkkitestitapauksessa hän kääntää ensin ensimmäisen nauhan kaikkien valojen tilan käyttäen liitäntöjä $0$ ja $3$, kustannuksella $1$. Sen jälkeen hän kääntää sen keskimmäisen valon tilan käyttäen liitäntöjä $1$ ja $2$, kustannuksella $100$. Kokonaiskustannus on $101$.