Little Cyan Fish hat zwei Lichtstreifen, die jeweils $n$ von $1$ bis $n$ nummerierte Lichter enthalten. Jedes Licht ist entweder ein- oder ausgeschaltet. Die Anfangszustände der beiden Streifen werden durch Binärstrings $a$ und $b$ der Länge $n$ beschrieben, wobei 1 ein eingeschaltetes Licht und 0 ein ausgeschaltetes Licht bezeichnet.

Es gibt $n + 1$ Steuerschnittstellen, die von $0$ bis $n$ nummeriert sind. Schnittstelle $0$ befindet sich vor dem ersten Licht, und Schnittstelle $i$ befindet sich für jedes $1 \le i \le n$ unmittelbar nach Licht $i$. Schnittstelle $i$ hat einen Kostenparameter $c_i$.

In einer Operation wählt Little Cyan Fish zwei Schnittstellen $p$ und $q$ ($0 \le p < q \le n$) und führt eine der folgenden Aktionen aus:

• Schalte alle Lichter mit den Nummern $p + 1, p + 2, \dots, q$ auf dem ersten Streifen um;
• Schalte alle Lichter mit den Nummern $p + 1, p + 2, \dots, q$ auf dem zweiten Streifen um;
• Schalte alle Lichter mit den Nummern $p + 1, p + 2, \dots, q$ auf beiden Streifen um.

Das Umschalten eines Lichts ändert seinen Zustand von eingeschaltet zu ausgeschaltet oder von ausgeschaltet zu eingeschaltet. Jede der drei Aktionen kostet $\max(c_p, c_q)$. Schnittstellen können wiederholt verwendet werden, und es gibt keine Begrenzung für die Anzahl der Operationen.

Bestimme die minimalen Gesamtkosten, die benötigt werden, um alle Lichter auf beiden Streifen auszuschalten.

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $T$ ($1 \le T$), die die Anzahl der Testfälle angibt.

Für jeden Testfall enthält die erste Zeile eine einzelne ganze Zahl $n$ ($1 \le n \le 3 \times 10^5$), die die Anzahl der Lichter auf jedem Streifen angibt.

Die zweite und dritte Zeile enthalten die Binärstrings $a$ bzw. $b$ der Länge $n$, die nur aus den Zeichen 0 und 1 bestehen.

Die vierte Zeile enthält $n + 1$ ganze Zahlen $c_0, c_1, \dots, c_n$ ($1 \le c_i \le 10^9$), die die Kostenparameter der Schnittstellen angeben.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle $3 \times 10^5$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine einzelne Zeile mit einer einzelnen ganzen Zahl aus, die die minimalen Gesamtkosten angibt, um alle Lichter auf beiden Streifen auszuschalten.

Beispiele

Eingabe 1

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

Ausgabe 1

0
9
101

Hinweis

Im ersten Beispieltestfall sind bereits alle Lichter ausgeschaltet, sodass keine Operation erforderlich ist.

Im zweiten Beispieltestfall wählt Little Cyan Fish die Schnittstellen $0$ und $1$ und schaltet beide Lichter um. Diese Operation kostet $\max(7, 9) = 9$.

Im dritten Beispieltestfall schaltet er zuerst alle Lichter auf dem ersten Streifen mithilfe der Schnittstellen $0$ und $3$ zu Kosten von $1$ um. Danach schaltet er dessen mittleres Licht mithilfe der Schnittstellen $1$ und $2$ zu Kosten von $100$ um. Die Gesamtkosten betragen $101$.