In einem langen Flur befinden sich $N$ Lampen in einer Reihe. Die Lampen sind von $1$ bis $N$ nummeriert. Jede Lampe ist entweder ausgeschaltet oder eingeschaltet. Es gibt einen besonderen Mechanismus, um die Zustände der Lampen zu ändern. In einer Operation können wir eine der folgenden Aktionen ausführen:

• Ganze Zahlen $p$ und $q$ mit $1 \le p \le q \le N$ wählen und die Lampen $p,p+1,\ldots,q$ ausschalten.
• Ganze Zahlen $p$ und $q$ mit $1 \le p \le q \le N$ wählen und die Lampen $p,p+1,\ldots,q$ einschalten.
• Ganze Zahlen $p$ und $q$ mit $1 \le p \le q \le N$ wählen und die Zustände der Lampen $p,p+1,\ldots,q$ umschalten (von ausgeschaltet zu eingeschaltet oder von eingeschaltet zu ausgeschaltet).

Die aktuellen Zustände der Lampen werden durch eine Zeichenkette $A$ der Länge $N$ dargestellt. Das $i$-te ($1 \le i \le N$) Zeichen von $A$ ist 0, wenn die Lampe $i$ ausgeschaltet ist, und 1, wenn sie eingeschaltet ist. Wir möchten die Lampen mit möglichst wenigen Operationen in die Zustände bringen, die durch eine Zeichenkette $B$ der Länge $N$ dargestellt werden. Das $i$-te ($1 \le i \le N$) Zeichen von $B$ ist 0, wenn die Lampe $i$ ausgeschaltet werden soll, und 1, wenn sie eingeschaltet werden soll.

Schreibe ein Programm, das anhand der Anzahl der Lampen, ihrer aktuellen Zustände und ihrer Zielzustände die minimale Anzahl von Operationen berechnet, die zum Erreichen der Zielzustände benötigt wird.

Eingabe

Lies die folgenden Daten von der Standardeingabe ein.

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

Ausgabe

Gib eine Zeile auf der Standardausgabe aus. Die Ausgabe soll die minimale Anzahl von Operationen enthalten, die zum Erreichen der Zielzustände benötigt wird.

Beschränkungen

• $1 \le N \le 1\,000\,000$.
• $A$ und $B$ sind Zeichenketten der Länge $N$.
• Jedes Zeichen in $A$ und $B$ ist entweder 0 oder 1.

Teilaufgaben

1. (6 Punkte) $N \le 18$.
2. (41 Punkte) $N \le 2\,000$.
3. (4 Punkte) Jedes Zeichen in $A$ ist 0.
4. (49 Punkte) Keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

8
11011100
01101001

Ausgabe 1

4

Hinweis

In dieser Beispieleingabe können wir die Zielzustände mit 4 Operationen erreichen, zum Beispiel wie folgt:

1. Schalte die Zustände der Lampen $1$, $2$, $3$ und $4$ um. Die Zustände der Lampen werden zu 00101100.
2. Schalte die Lampe $2$ ein. Die Zustände der Lampen werden zu 01101100.
3. Schalte die Zustände der Lampen $6$, $7$ und $8$ um. Die Zustände der Lampen werden zu 01101011.
4. Schalte die Lampen $6$ und $7$ aus. Die Zustände der Lampen werden zu 01101001.

Da es unmöglich ist, die Zielzustände mit weniger als 4 Operationen zu erreichen, gib 4 aus.

Eingabe 2

13
1010010010100
0000111001011

Ausgabe 2

3

Eingabe 3

18
001100010010000110
110110001000100101

Ausgabe 3

5