Little Cyan Fish-те екі жарық жолағы бар, олардың әрқайсысында $1$-ден $n$-ге дейін нөмірленген $n$ шам бар. Әрбір шам не қосулы, не өшірулі. Екі жолақтың бастапқы күйлері ұзындығы $n$ болатын $a$ және $b$ екілік жолдарымен сипатталады, мұндағы 1 қосулы шамды, ал 0 өшірулі шамды білдіреді.

$0$-ден $n$-ге дейін нөмірленген $n + 1$ басқару интерфейсі бар. $0$ интерфейсі бірінші шамның алдында, ал $i$ интерфейсі әрбір $1 \le i \le n$ үшін $i$-ші шамнан кейін бірден орналасқан. $i$ интерфейсінің $c_i$ құн параметрі бар.

Бір операцияда Little Cyan Fish екі $p$ және $q$ ($0 \le p < q \le n$) интерфейсін таңдап, келесі әрекеттердің бірін орындайды:

• Бірінші жолақтағы $p + 1, p + 2, \dots, q$ деп нөмірленген барлық шамдардың күйін ауыстыру;
• Екінші жолақтағы $p + 1, p + 2, \dots, q$ деп нөмірленген барлық шамдардың күйін ауыстыру;
• Екі жолақтағы да $p + 1, p + 2, \dots, q$ деп нөмірленген барлық шамдардың күйін ауыстыру.

Шамның күйін ауыстыру оның күйін қосулыдан өшіруліге немесе өшіруліден қосулыға өзгертеді. Үш әрекеттің әрқайсысының құны $\max(c_p, c_q)$ құрайды. Интерфейстерді қайталап пайдалануға болады, ал операциялар санына шектеу қойылмайды.

Екі жолақтағы барлық шамдарды өшіру үшін қажетті ең аз жалпы құнды табыңыз.

Кіріс деректер

Бірнеше тест жағдайлары бар. Кірістің бірінші жолында тест жағдайларының санын білдіретін бір бүтін сан $T$ ($1 \le T$) берілген.

Әрбір тест жағдайы үшін бірінші жолда әр жолақтағы шамдар санын білдіретін бір бүтін сан $n$ ($1 \le n \le 3 \times 10^5$) берілген.

Екінші және үшінші жолдарда сәйкесінше тек 0 және 1 таңбаларынан тұратын, ұзындығы $n$ болатын $a$ және $b$ екілік жолдары берілген.

Төртінші жолда интерфейстердің құн параметрлерін білдіретін $n + 1$ бүтін сан $c_0, c_1, \dots, c_n$ ($1 \le c_i \le 10^9$) берілген.

Барлық тест жағдайлары бойынша $n$ сандарының қосындысы $3 \times 10^5$-нен аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест жағдайы үшін екі жолақтағы барлық шамдарды өшіруге қажетті ең аз жалпы құнды білдіретін бір бүтін саннан тұратын бір жолды шығарыңыз.

Мысалдар

Кіріс 1

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

Шығыс 1

0
9
101

Ескертпе

Бірінші мысалдағы тест жағдайында барлық шамдар бастапқыда өшірулі, сондықтан ешқандай операция қажет емес.

Екінші мысалдағы тест жағдайында Little Cyan Fish $0$ және $1$ интерфейстерін таңдап, екі шамның да күйін ауыстырады. Бұл операцияның құны $\max(7, 9) = 9$.

Үшінші мысалдағы тест жағдайында ол алдымен $0$ және $3$ интерфейстерін пайдаланып, бірінші жолақтағы барлық шамдардың күйін $1$ құнымен ауыстырады. Содан кейін ол $1$ және $2$ интерфейстерін пайдаланып, оның ортаңғы шамының күйін $100$ құнымен ауыстырады. Жалпы құны — $101$.