E. Сдвиги подпоследовательностей
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Naman есть две бинарные строки $$$s$$$ и $$$t$$$ длины $$$n$$$ (бинарной строкой называется строка, состоящая из символов «0» и «1»). Он хочет сделать из строки $$$s$$$ строку $$$t$$$ используя следующую операцию как можно меньшее количество раз.

За одну операцию, он может выбрать некоторую подпоследовательность $$$s$$$ и сдвинуть символы на позициях этой подпоследовательности по часовой стрелке один раз.

Например, если $$$s = 1\textbf{1}101\textbf{00}$$$, он может выбрать подпоследовательность, соответствущую позициям (нумерация с $$$1$$$) $$$\{2, 6, 7 \}$$$ и сдвинуть символы на этих позициях один раз по часовой стрелке. В результате строка, которая получится, будет $$$s = 1\textbf{0}101\textbf{10}$$$.

Строка $$$a$$$ называется подпоследовательностью строки $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ с помощью удаления некоторых символов без изменения порядка оставшихся символов.

Для того, чтобы сделать сдвиг последовательности $$$c$$$ размера $$$k$$$ по часовой стрелке один раз, нужно сделать следующие замены символов $$$c_1:=c_k, c_2:=c_1, c_3:=c_2, \ldots, c_k:=c_{k-1}$$$ одновременно.

Определите минимальное число операций, которое необходимо сделать Naman, чтобы получить из строки $$$s$$$ строку $$$t$$$ или определите, что это сделать невозможно.

Входные данные

В первой строке находится единственное целое число $$$n$$$ $$$(1 \le n \le 10^6)$$$ — длина строк.

Во второй строке находится бинарная строка $$$s$$$ длины $$$n$$$.

В третьей строке находится бинарная строка $$$t$$$ длины $$$n$$$.

Выходные данные

Если невозможно получить из строки $$$s$$$ строку $$$t$$$ после применения любого числа операций, выведите $$$-1$$$.

Иначе выведите минимальное количество операций, которое для этого требуется.

Примеры
Входные данные
6
010000
000001
Выходные данные
1
Входные данные
10
1111100000
0000011111
Выходные данные
5
Входные данные
8
10101010
01010101
Выходные данные
1
Входные данные
10
1111100000
1111100001
Выходные данные
-1
Примечание

В первом тесте, Naman может выбрать подпоследовательность, соответствующую позициям $$$\{2, 6\}$$$ и сдвинуть символы строки, на этих позициях один раз по часовой стрелке. В результате, он сможет получить из строки $$$s$$$ строку $$$t$$$ за одну операцию.

Во втором тесте, он может сделать операцию на подпоследовательности из всех индексов $$$5$$$ раз подряд. Можно доказать, что это минимальное необходимое количество операций.

В последнем тесте, невозможно получить из строки $$$s$$$ строку $$$t$$$.