Có $N$ bóng đèn xếp thành một hàng trong một hành lang dài. Các bóng đèn được đánh số từ $1$ đến $N$. Mỗi bóng đèn có một trong hai trạng thái: tắt hoặc bật. Có một cơ chế đặc biệt để thay đổi trạng thái của các bóng đèn. Trong một thao tác, ta có thể thực hiện một trong những việc sau:

• Chọn các số nguyên $p$ và $q$ thỏa mãn $1\le p\le q\le N$, rồi tắt các bóng đèn $p,p+1,\ldots,q$.
• Chọn các số nguyên $p$ và $q$ thỏa mãn $1\le p\le q\le N$, rồi bật các bóng đèn $p,p+1,\ldots,q$.
• Chọn các số nguyên $p$ và $q$ thỏa mãn $1\le p\le q\le N$, rồi đảo trạng thái của các bóng đèn $p,p+1,\ldots,q$ (từ tắt sang bật hoặc từ bật sang tắt).

Trạng thái hiện tại của các bóng đèn được biểu diễn bằng một xâu $A$ có độ dài $N$. Ký tự thứ $i$ ($1\le i\le N$) của $A$ là 0 nếu bóng đèn $i$ đang tắt và là 1 nếu đang bật. Ta muốn chuyển trạng thái của các bóng đèn thành trạng thái được biểu diễn bằng một xâu $B$ có độ dài $N$, với số thao tác ít nhất có thể. Ký tự thứ $i$ ($1\le i\le N$) của $B$ là 0 nếu ta muốn bóng đèn $i$ tắt và là 1 nếu muốn nó bật.

Hãy viết một chương trình nhận số bóng đèn, trạng thái hiện tại và trạng thái đích, rồi tính số thao tác ít nhất cần thực hiện để đạt được trạng thái đích.

Dữ liệu vào

Đọc dữ liệu sau từ đầu vào chuẩn.

$$ \begin{array}{l} N \\ A \\ B \end{array} $$

Dữ liệu ra

Ghi một dòng ra đầu ra chuẩn. Dòng này phải chứa số thao tác ít nhất cần thực hiện để đạt được trạng thái đích.

Giới hạn

• $1\le N\le 1\,000\,000$.
• $A$ và $B$ là các xâu có độ dài $N$.
• Mỗi ký tự trong $A$ và $B$ là 0 hoặc 1.

Nhiệm vụ con

1. (6 điểm) $N\le 18$.
2. (41 điểm) $N\le 2\,000$.
3. (4 điểm) Mỗi ký tự trong $A$ là 0.
4. (49 điểm) Không có giới hạn bổ sung.

Ví dụ

Dữ liệu vào 1

8
11011100
01101001

Dữ liệu ra 1

4

Ghi chú

Trong ví dụ này, ta có thể đạt được trạng thái đích sau 4 thao tác, chẳng hạn như sau:

1. Đảo trạng thái các bóng đèn $1$, $2$, $3$ và $4$. Trạng thái các bóng đèn trở thành 00101100.
2. Bật bóng đèn $2$. Trạng thái các bóng đèn trở thành 01101100.
3. Đảo trạng thái các bóng đèn $6$, $7$ và $8$. Trạng thái các bóng đèn trở thành 01101011.
4. Tắt các bóng đèn $6$ và $7$. Trạng thái các bóng đèn trở thành 01101001.

Vì không thể đạt được trạng thái đích với ít hơn 4 thao tác, hãy in ra 4.

Dữ liệu vào 2

13
1010010010100
0000111001011

Dữ liệu ra 2

3

Dữ liệu vào 3

18
001100010010000110
110110001000100101

Dữ liệu ra 3

5