มีหลอดไฟ $N$ หลอดเรียงกันเป็นแถวในทางเดินยาว หลอดไฟมีหมายเลขตั้งแต่ $1$ ถึง $N$ หลอดไฟแต่ละหลอดมีสถานะเปิดหรือปิด มีกลไกพิเศษสำหรับเปลี่ยนสถานะของหลอดไฟ ในการดำเนินการหนึ่งครั้ง เราสามารถทำอย่างใดอย่างหนึ่งต่อไปนี้ได้:

• เลือกจำนวนเต็ม $p$ และ $q$ ที่ $1 \le p \le q \le N$ แล้วปิดหลอดไฟ $p, p+1, \ldots, q$
• เลือกจำนวนเต็ม $p$ และ $q$ ที่ $1 \le p \le q \le N$ แล้วเปิดหลอดไฟ $p, p+1, \ldots, q$
• เลือกจำนวนเต็ม $p$ และ $q$ ที่ $1 \le p \le q \le N$ แล้วสลับสถานะของหลอดไฟ $p, p+1, \ldots, q$ (จากปิดเป็นเปิด หรือจากเปิดเป็นปิด)

สถานะปัจจุบันของหลอดไฟแทนด้วยสตริง $A$ ที่มีความยาว $N$ อักขระตัวที่ $i$ ($1 \le i \le N$) ของ $A$ เป็น 0 ถ้าหลอดไฟ $i$ ปิดอยู่ และเป็น 1 ถ้าเปิดอยู่ เราต้องการเปลี่ยนสถานะของหลอดไฟให้เป็นสถานะที่แทนด้วยสตริง $B$ ที่มีความยาว $N$ โดยใช้จำนวนครั้งในการดำเนินการให้น้อยที่สุด อักขระตัวที่ $i$ ($1 \le i \le N$) ของ $B$ เป็น 0 ถ้าเราต้องการให้หลอดไฟ $i$ ปิด และเป็น 1 ถ้าต้องการให้เปิด

จงเขียนโปรแกรมที่รับจำนวนหลอดไฟ สถานะปัจจุบัน และสถานะเป้าหมาย แล้วคำนวณจำนวนครั้งน้อยที่สุดในการดำเนินการที่จำเป็นเพื่อให้ได้สถานะเป้าหมาย

ข้อมูลนำเข้า

อ่านข้อมูลต่อไปนี้จากข้อมูลนำเข้ามาตรฐาน

N
A
B

ข้อมูลส่งออก

เขียนข้อมูลหนึ่งบรรทัดไปยังข้อมูลส่งออกมาตรฐาน โดยให้มีจำนวนครั้งน้อยที่สุดในการดำเนินการที่จำเป็นเพื่อให้ได้สถานะเป้าหมาย

ข้อจำกัด

• $1 \le N \le 1\,000\,000$
• $A$ และ $B$ เป็นสตริงที่มีความยาว $N$
• อักขระแต่ละตัวใน $A$ และ $B$ เป็น 0 หรือ 1

งานย่อย

1. (6 คะแนน) $N \le 18$
2. (41 คะแนน) $N \le 2\,000$
3. (4 คะแนน) อักขระทุกตัวใน $A$ เป็น 0
4. (49 คะแนน) ไม่มีข้อจำกัดเพิ่มเติม

ตัวอย่าง

ข้อมูลนำเข้า 1

8
11011100
01101001

ข้อมูลส่งออก 1

4

หมายเหตุ

ในตัวอย่างนี้ เราสามารถทำให้ได้สถานะเป้าหมายด้วยการดำเนินการ 4 ครั้ง เช่น ดังต่อไปนี้:

1. สลับสถานะของหลอดไฟ $1, 2, 3$ และ $4$ สถานะของหลอดไฟจะกลายเป็น 00101100
2. เปิดหลอดไฟ $2$ สถานะของหลอดไฟจะกลายเป็น 01101100
3. สลับสถานะของหลอดไฟ $6, 7$ และ $8$ สถานะของหลอดไฟจะกลายเป็น 01101011
4. ปิดหลอดไฟ $6$ และ $7$ สถานะของหลอดไฟจะกลายเป็น 01101001

เนื่องจากไม่สามารถทำให้ได้สถานะเป้าหมายด้วยการดำเนินการน้อยกว่า 4 ครั้ง จึงส่งออก 4

ข้อมูลนำเข้า 2

13
1010010010100
0000111001011

ข้อมูลส่งออก 2

3

ข้อมูลนำเข้า 3

18
001100010010000110
110110001000100101

ข้อมูลส่งออก 3

5