Little Cyan Fish ma dwa paski świetlne, z których każdy zawiera $n$ lampek ponumerowanych od $1$ do $n$. Każda lampka jest albo włączona, albo wyłączona. Początkowe stany obu pasków opisane są ciągami binarnymi $a$ oraz $b$ o długości $n$, gdzie 1 oznacza włączoną lampkę, a 0 oznacza wyłączoną lampkę.

Istnieje $n + 1$ interfejsów sterujących, ponumerowanych od $0$ do $n$. Interfejs $0$ znajduje się przed pierwszą lampką, a interfejs $i$ znajduje się bezpośrednio za lampką $i$ dla każdego $1 \le i \le n$. Interfejs $i$ ma parametr kosztu $c_i$.

W jednej operacji Little Cyan Fish wybiera dwa interfejsy $p$ i $q$ ($0 \le p < q \le n$) oraz wykonuje jedną z następujących akcji:

• Przełącz wszystkie lampki o numerach $p + 1, p + 2, \dots, q$ na pierwszym pasku;
• Przełącz wszystkie lampki o numerach $p + 1, p + 2, \dots, q$ na drugim pasku;
• Przełącz wszystkie lampki o numerach $p + 1, p + 2, \dots, q$ na obu paskach.

Przełączenie lampki zmienia jej stan z włączonej na wyłączoną lub z wyłączonej na włączoną. Każda z trzech akcji kosztuje $\max(c_p, c_q)$. Interfejsów można używać wielokrotnie i nie ma ograniczenia na liczbę operacji.

Znajdź minimalny łączny koszt potrzebny do wyłączenia wszystkich lampek na obu paskach.

Wejście

Test składa się z wielu przypadków testowych. Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $T$ ($1 \le T$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 3 \times 10^5$), oznaczającą liczbę lampek na każdym pasku.

Drugi i trzeci wiersz zawierają odpowiednio ciągi binarne $a$ i $b$ o długości $n$, składające się wyłącznie ze znaków 0 oraz 1.

Czwarty wiersz zawiera $n + 1$ liczb całkowitych $c_0, c_1, \dots, c_n$ ($1 \le c_i \le 10^9$), oznaczających parametry kosztu interfejsów.

Gwarantowane jest, że suma $n$ po wszystkich przypadkach testowych nie przekracza $3 \times 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający jedną liczbę całkowitą, oznaczającą minimalny łączny koszt potrzebny do wyłączenia wszystkich lampek na obu paskach.

Przykład

Wejście 1

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

Wyjście 1

0
9
101

Uwagi

W pierwszym przykładowym przypadku testowym wszystkie lampki są już wyłączone, więc żadna operacja nie jest potrzebna.

W drugim przykładowym przypadku testowym Little Cyan Fish wybiera interfejsy $0$ oraz $1$ i przełącza obie lampki. Ta operacja kosztuje $\max(7, 9) = 9$.

W trzecim przykładowym przypadku testowym najpierw przełącza wszystkie lampki na pierwszym pasku za pomocą interfejsów $0$ oraz $3$, kosztem $1$. Następnie przełącza jego środkową lampkę za pomocą interfejsów $1$ oraz $2$, kosztem $100$. Łączny koszt wynosi $101$.