codeforces#P1370E. Binary Subsequence Rotation

    ID: 31254 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>binary searchconstructive algorithmsdata structuresgreedy*2100

Binary Subsequence Rotation

Description

Naman has two binary strings $s$ and $t$ of length $n$ (a binary string is a string which only consists of the characters "0" and "1"). He wants to convert $s$ into $t$ using the following operation as few times as possible.

In one operation, he can choose any subsequence of $s$ and rotate it clockwise once.

For example, if $s = 1\textbf{1}101\textbf{00}$, he can choose a subsequence corresponding to indices ($1$-based) $\{2, 6, 7 \}$ and rotate them clockwise. The resulting string would then be $s = 1\textbf{0}101\textbf{10}$.

A string $a$ is said to be a subsequence of string $b$ if $a$ can be obtained from $b$ by deleting some characters without changing the ordering of the remaining characters.

To perform a clockwise rotation on a sequence $c$ of size $k$ is to perform an operation which sets $c_1:=c_k, c_2:=c_1, c_3:=c_2, \ldots, c_k:=c_{k-1}$ simultaneously.

Determine the minimum number of operations Naman has to perform to convert $s$ into $t$ or say that it is impossible.

The first line contains a single integer $n$ $(1 \le n \le 10^6)$ — the length of the strings.

The second line contains the binary string $s$ of length $n$.

The third line contains the binary string $t$ of length $n$.

If it is impossible to convert $s$ to $t$ after any number of operations, print $-1$.

Otherwise, print the minimum number of operations required.

Input

The first line contains a single integer $n$ $(1 \le n \le 10^6)$ — the length of the strings.

The second line contains the binary string $s$ of length $n$.

The third line contains the binary string $t$ of length $n$.

Output

If it is impossible to convert $s$ to $t$ after any number of operations, print $-1$.

Otherwise, print the minimum number of operations required.

Samples

6
010000
000001
1
10
1111100000
0000011111
5
8
10101010
01010101
1
10
1111100000
1111100001
-1

Note

In the first test, Naman can choose the subsequence corresponding to indices $\{2, 6\}$ and rotate it once to convert $s$ into $t$.

In the second test, he can rotate the subsequence corresponding to all indices $5$ times. It can be proved, that it is the minimum required number of operations.

In the last test, it is impossible to convert $s$ into $t$.