Il y a $N$ lampes alignées dans un long couloir. Les lampes sont numérotées de $1$ à $N$. Chaque lampe est soit éteinte, soit allumée. Un mécanisme spécial permet de modifier l'état des lampes. En une opération, on peut effectuer l'une des actions suivantes :

• Choisir des entiers $p$ et $q$ tels que $1 \le p \le q \le N$, et éteindre les lampes $p, p+1, \ldots, q$.
• Choisir des entiers $p$ et $q$ tels que $1 \le p \le q \le N$, et allumer les lampes $p, p+1, \ldots, q$.
• Choisir des entiers $p$ et $q$ tels que $1 \le p \le q \le N$, et inverser l'état des lampes $p, p+1, \ldots, q$ (d'éteint à allumé, ou d'allumé à éteint).

Les états actuels des lampes sont représentés par une chaîne $A$ de longueur $N$. Le $i$-ème caractère de $A$ ($1 \le i \le N$) vaut 0 si la lampe $i$ est éteinte, et 1 si elle est allumée. Nous souhaitons obtenir les états représentés par une chaîne $B$ de longueur $N$, en effectuant le moins d'opérations possible. Le $i$-ème caractère de $B$ ($1 \le i \le N$) vaut 0 si nous souhaitons éteindre la lampe $i$, et 1 si nous souhaitons l'allumer.

Écrivez un programme qui, étant donnés le nombre de lampes, leurs états actuels et leurs états cibles, calcule le nombre minimal d'opérations nécessaires pour atteindre les états cibles.

Entrée

Lisez les données suivantes sur l'entrée standard.

$$ N\\ A\\ B $$

Sortie

Écrivez une ligne sur la sortie standard. Elle doit contenir le nombre minimal d'opérations nécessaires pour atteindre les états cibles.

Contraintes

• $1 \le N \le 1\,000\,000$.
• $A$ et $B$ sont des chaînes de longueur $N$.
• Chaque caractère de $A$ et de $B$ est soit 0, soit 1.

Sous-tâches

1. (6 points) $N \le 18$.
2. (41 points) $N \le 2\,000$.
3. (4 points) Chaque caractère de $A$ est 0.
4. (49 points) Aucune contrainte supplémentaire.

Exemples

Entrée 1

8
11011100
01101001

Sortie 1

4

Remarque

Dans cet exemple, nous pouvons atteindre les états cibles en $4$ opérations, par exemple comme suit :

1. Inverser l'état des lampes $1, 2, 3$ et $4$. Les états des lampes deviennent 00101100.
2. Allumer la lampe $2$. Les états des lampes deviennent 01101100.
3. Inverser l'état des lampes $6, 7$ et $8$. Les états des lampes deviennent 01101011.
4. Éteindre les lampes $6$ et $7$. Les états des lampes deviennent 01101001.

Puisqu'il est impossible d'atteindre les états cibles en moins de $4$ opérations, affichez $4$.

Entrée 2

13
1010010010100
0000111001011

Sortie 2

3

Entrée 3

18
001100010010000110
110110001000100101

Sortie 3

5