Little Cyan Fish har två ljusremsor som var och en innehåller $n$ lampor numrerade från $1$ till $n$. Varje lampa är antingen tänd eller släckt. De ursprungliga tillstånden för de två remsorna beskrivs av de binära strängarna $a$ och $b$ med längden $n$, där 1 betecknar en tänd lampa och 0 betecknar en släckt lampa.

Det finns $n + 1$ kontrollgränssnitt, numrerade från $0$ till $n$. Gränssnitt $0$ ligger före den första lampan, och gränssnitt $i$ ligger omedelbart efter lampa $i$ för varje $1 \le i \le n$. Gränssnitt $i$ har en kostnadsparameter $c_i$.

I en operation väljer Little Cyan Fish två gränssnitt $p$ och $q$ ($0 \le p < q \le n$) och utför en av följande åtgärder:

• Växla alla lampor numrerade $p + 1, p + 2, \dots, q$ på den första remsan;
• Växla alla lampor numrerade $p + 1, p + 2, \dots, q$ på den andra remsan;
• Växla alla lampor numrerade $p + 1, p + 2, \dots, q$ på båda remsorna.

Att växla en lampa ändrar dess tillstånd från tänd till släckt eller från släckt till tänd. Var och en av de tre åtgärderna kostar $\max(c_p, c_q)$. Gränssnitt får användas upprepade gånger, och det finns ingen gräns för antalet operationer.

Hitta den minsta totala kostnaden som krävs för att släcka alla lampor på båda remsorna.

Indata

Det finns flera testfall. Den första raden i indatan innehåller ett enda heltal $T$ ($1 \le T$), som anger antalet testfall.

För varje testfall innehåller den första raden ett enda heltal $n$ ($1 \le n \le 3 \times 10^5$), som anger antalet lampor på varje remsa.

Den andra och tredje raden innehåller de binära strängarna $a$ respektive $b$ med längden $n$, som endast består av tecknen 0 och 1.

Den fjärde raden innehåller $n + 1$ heltal $c_0, c_1, \dots, c_n$ ($1 \le c_i \le 10^9$), som anger kostnadsparametrarna för gränssnitten.

Det garanteras att summan av $n$ över alla testfall inte överstiger $3 \times 10^5$.

Utdata

För varje testfall, skriv ut en enda rad som innehåller ett enda heltal, vilket anger den minsta totala kostnaden som krävs för att släcka alla lampor på båda remsorna.

Exempel

Indata 1

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

Utdata 1

0
9
101

Förklaring

I det första exempeltestfallet är alla lampor redan släckta, så ingen operation behövs.

I det andra exempeltestfallet väljer Little Cyan Fish gränssnitten $0$ och $1$ och växlar båda lamporna. Denna operation kostar $\max(7, 9) = 9$.

I det tredje exempeltestfallet växlar han först alla lampor på den första remsan med hjälp av gränssnitten $0$ och $3$, till kostnaden $1$. Därefter växlar han dess mittersta lampa med hjälp av gränssnitten $1$ och $2$, till kostnaden $100$. Den totala kostnaden är $101$.