Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Binary Subsequence Rotation

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputNaman 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.

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.

Examples

Input

6 010000 000001

Output

1

Input

10 1111100000 0000011111

Output

5

Input

8 10101010 01010101

Output

1

Input

10 1111100000 1111100001

Output

-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$$$.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/13/2021 21:47:07 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|