Há $N$ lâmpadas dispostas em fila num longo corredor. As lâmpadas são numeradas de $1$ a $N$. Cada lâmpada está apagada ou acesa. Existe um mecanismo especial para alterar os estados das lâmpadas. Numa operação, podemos realizar uma das seguintes ações:

• Escolher inteiros $p$ e $q$ com $1 \le p \le q \le N$ e apagar as lâmpadas $p, p+1, \ldots, q$.
• Escolher inteiros $p$ e $q$ com $1 \le p \le q \le N$ e acender as lâmpadas $p, p+1, \ldots, q$.
• Escolher inteiros $p$ e $q$ com $1 \le p \le q \le N$ e inverter os estados das lâmpadas $p, p+1, \ldots, q$ (de apagada para acesa, ou de acesa para apagada).

Os estados atuais das lâmpadas são representados por uma cadeia $A$ de comprimento $N$. O $i$-ésimo ($1 \le i \le N$) caráter de $A$ é 0 se a lâmpada $i$ está apagada, e 1 se está acesa. Queremos que os estados das lâmpadas passem a ser os representados por uma cadeia $B$ de comprimento $N$, com o menor número possível de operações. O $i$-ésimo ($1 \le i \le N$) caráter de $B$ é 0 se queremos apagar a lâmpada $i$, e 1 se queremos acendê-la.

Escreva um programa que, dados o número de lâmpadas, os estados atuais e os estados pretendidos, calcule o número mínimo de operações necessárias para atingir os estados pretendidos.

Entrada

Leia os seguintes dados da entrada padrão.

N
A
B

Saída

Escreva uma linha na saída padrão. A saída deve conter o número mínimo de operações necessárias para atingir os estados pretendidos.

Restrições

• $1 \le N \le 1\,000\,000$.
• $A$ e $B$ são cadeias de comprimento $N$.
• Cada caráter de $A$ e $B$ é 0 ou 1.

Subtarefas

1. (6 pontos) $N \le 18$.
2. (41 pontos) $N \le 2\,000$.
3. (4 pontos) Cada caráter de $A$ é 0.
4. (49 pontos) Sem restrições adicionais.

Exemplos

Entrada 1

8
11011100
01101001

Saída 1

4

Nota

Neste exemplo de entrada, podemos atingir os estados pretendidos em 4 operações, por exemplo, da seguinte forma:

1. Inverta os estados das lâmpadas $1$, $2$, $3$ e $4$. Os estados das lâmpadas passam a ser 00101100.
2. Acenda a lâmpada $2$. Os estados das lâmpadas passam a ser 01101100.
3. Inverta os estados das lâmpadas $6$, $7$ e $8$. Os estados das lâmpadas passam a ser 01101011.
4. Apague as lâmpadas $6$ e $7$. Os estados das lâmpadas passam a ser 01101001.

Como é impossível atingir os estados pretendidos em menos de 4 operações, imprima 4.

Entrada 2

13
1010010010100
0000111001011

Saída 2

3

Entrada 3

18
001100010010000110
110110001000100101

Saída 3

5