Un tablón de anuncios eléctrico muestra una cadena ~S~ de longitud ~N~ que consiste de ~0~ y ~1~. Usted puede realizar la siguiente operación cualquier número de veces, donde ~S_{i}~ denota el ~i~-ésimo caracter ~(1 \leq i \leq N)~ de la cadena mostrada en el tablón.

Operación: seleccione un par de enteros ~(l,r)(1 \leq l < r \leq N)~ que cumplan una de las condiciones siguientes y cambie ~S_{l}~ por ~S_{r}~.

• ~S_{l} = 0~ y ~S_{l+1} = \ldots = S_{r} = 1~.
• ~S_{l} = \ldots = S_{r-1} = 1~ y ~S_{r} = 0~.

Determine si es posible hacer que la cadena que se muestra en el tablón coincida con la cadena ~T~ dada, y encuentre el número mínimo de operaciones necesarias si es posible.

Restricciones

• ~2 \leq N \leq 500\,000~.
• ~S~ es una cadena de longitud ~N~ que consiste de ~0~ y ~1~.
• ~T~ es una cadena de longitud ~N~ que consiste de ~0~ y ~1~.

Subtareas

• ~N \leq 5000~ ~(30\,puntos)~
• Sin restricción adicional ~(70\,puntos)~

Entrada

La primera línea contiene un entero ~N~, la segunda línea contiene una cadena ~S~ y la tercera línea contiene una cadena ~T~.

Salida

Si es imposible que el tablón muestre la cadena ~T~, imprima ~-1~. De ser posible encuentre el mínimo número de operaciones necesarias.

Ejemplos

Entrada 1

7
1110110
1010111

Salida 1

2

Aquí hay una forma posible de hacer que el tablón muestre la cadena ~1010111~ en dos operaciones:

• Haz la operación con ~(l,r) = (2,4)~, cambiando la cadena en el tablón de ~1110110~ a ~1011110~.
• Haz la operación con ~(l,r) = (4,7)~, cambiando la cadena en el tablón de ~1011110~ a ~1010111~.

Entrada 2

20
11111000000000011111
11111000000000011111

Salida 2

0

El tablón ya muestra la cadena ~T~ antes de realizar cualquier operación, por lo que la respuesta es ~0~.

Entrada 3

6
111100
111000

Salida 3

-1

Si no hay una secuencia de operaciones que haga que el tablón muestre la cadena ~T~, imprima ~-1~.

Entrada 4

119
10101111011101001011111000111111101011110011010111111111111111010111111111111110111111110111110111101111111111110111011
11111111111111111111111111011111101011111011110111110010100101001110111011110111111111110010011111101111111101110111011

Salida 4

22