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$