لدى Little Cyan Fish شريطا إضاءة، يحتوي كل منهما على $n$ من المصابيح المرقمة من $1$ إلى $n$. كل مصباح إما مضاء أو مطفأ. تُوصف الحالات الابتدائية للشريطين بسلسلتين ثنائيتين $a$ و $b$ طول كل منهما $n$، حيث يرمز 1 إلى مصباح مضاء ويرمز 0 إلى مصباح مطفأ.
توجد $n + 1$ واجهات تحكم، مرقمة من $0$ إلى $n$. تقع الواجهة $0$ قبل المصباح الأول، وتقع الواجهة $i$ مباشرةً بعد المصباح $i$ لكل $1 \le i \le n$. للواجهة $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$)، يشير إلى عدد المصابيح في كل شريط.
يحتوي السطران الثاني والثالث على سلسلتين ثنائيتين $a$ و $b$ طول كل منهما $n$، على التوالي، وتتكونان فقط من المحرفين 0 و 1.
يحتوي السطر الرابع على $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$.