ל-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$.