Little Cyan Fish memiliki dua strip lampu, yang masing-masing berisi $n$ lampu berlabel dari $1$ hingga $n$. Setiap lampu berada dalam keadaan menyala atau mati. Keadaan awal dari kedua strip tersebut dideskripsikan oleh string biner $a$ dan $b$ dengan panjang $n$, di mana 1 menyatakan lampu yang menyala dan 0 menyatakan lampu yang mati.

Terdapat $n + 1$ antarmuka kontrol, yang diberi label dari $0$ hingga $n$. Antarmuka $0$ berada sebelum lampu pertama, dan antarmuka $i$ berada tepat setelah lampu $i$ untuk setiap $1 \le i \le n$. Antarmuka $i$ memiliki parameter biaya $c_i$.

Dalam satu operasi, Little Cyan Fish memilih dua antarmuka $p$ dan $q$ ($0 \le p < q \le n$) dan melakukan salah satu dari tindakan berikut:

• Membalik keadaan semua lampu berlabel $p + 1, p + 2, \dots, q$ pada strip pertama;
• Membalik keadaan semua lampu berlabel $p + 1, p + 2, \dots, q$ pada strip kedua;
• Membalik keadaan semua lampu berlabel $p + 1, p + 2, \dots, q$ pada kedua strip.

Membalik keadaan sebuah lampu mengubah keadaannya dari menyala menjadi mati atau dari mati menjadi menyala. Masing-masing dari ketiga tindakan tersebut membutuhkan biaya $\max(c_p, c_q)$. Antarmuka dapat digunakan berulang kali, dan tidak ada batasan jumlah operasi.

Carilah total biaya minimum yang diperlukan untuk mematikan semua lampu pada kedua strip.

Masukan

Terdapat beberapa kasus uji. Baris pertama dari masukan berisi sebuah bilangan bulat $T$ ($1 \le T$), yang menyatakan jumlah kasus uji.

Untuk setiap kasus uji, baris pertama berisi sebuah bilangan bulat $n$ ($1 \le n \le 3 \times 10^5$), yang menyatakan jumlah lampu pada setiap strip.

Baris kedua dan ketiga masing-masing berisi string biner $a$ dan $b$ dengan panjang $n$, yang hanya terdiri dari karakter 0 dan 1.

Baris keempat berisi $n + 1$ bilangan bulat $c_0, c_1, \dots, c_n$ ($1 \le c_i \le 10^9$), yang menyatakan parameter biaya dari antarmuka-antarmuka tersebut.

Dijamin bahwa jumlah $n$ di seluruh kasus uji tidak melebihi $3 \times 10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris yang berisi sebuah bilangan bulat, yang menyatakan total biaya minimum yang diperlukan untuk mematikan semua lampu pada kedua strip.

Contoh

Masukan 1

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

Keluaran 1

0
9
101

Catatan

Pada kasus uji contoh pertama, semua lampu sudah mati, sehingga tidak diperlukan operasi apa pun.

Pada kasus uji contoh kedua, Little Cyan Fish memilih antarmuka $0$ dan $1$ lalu membalik keadaan kedua lampu. Operasi ini membutuhkan biaya $\max(7, 9) = 9$.

Pada kasus uji contoh ketiga, pertama-tama ia membalik keadaan semua lampu pada strip pertama menggunakan antarmuka $0$ dan $3$, dengan biaya $1$. Ia kemudian membalik keadaan lampu tengahnya menggunakan antarmuka $1$ dan $2$, dengan biaya $100$. Total biayanya adalah $101$.