F. Пазл
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Школьники Алиса и Ибрагим — лучшие друзья. У Ибрагима скоро день рождения, и по этому поводу Алиса решила подарить ему новый пазл. Пазл можно представить в виде матрицы из $$$2$$$ строк и $$$n$$$ столбцов, каждый элемент которой — $$$0$$$, либо $$$1$$$. За один ход можно поменять местами два элемента, стоящие в соседних клетках.

Более формально, будем считать, что строки матриц пронумерованы сверху вниз от $$$1$$$ до $$$2$$$, а столбцы — слева направо от $$$1$$$ до $$$n$$$. Обозначим клетку на пересечении строки $$$x$$$ и столбца $$$y$$$ за $$$(x, y)$$$. Будем считать две клетки $$$(x_1, y_1)$$$ и $$$(x_2, y_2)$$$ соседними, если $$$|x_1 - x_2| + |y_1 - y_2| = 1$$$.

Алисе не нравится, какой рисунок образуют клетки пазла в данный момент. Она придумала свой рисунок, с которым и планирует подарить Ибрагиму новый пазл. Помогите Алисе найти минимальное количество ходов, за которое она может получить свой рисунок, или скажите, что это невозможно.

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

В первой строке записано число $$$n$$$ ($$$1 \leq n \leq 200\,000$$$) — количество столбцов в пазле.

Следующие две строки описывают рисунок, образованный пазлом в данный момент. В каждой строке записано $$$n$$$ чисел, каждое из которых равно либо $$$0$$$, либо $$$1$$$.

Следующие две строки описывают желаемый рисунок Алисы в том же формате.

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

Если Алиса не ошиблась и её рисунок можно получить — найдите и выведите минимальное необходимое количество ходов, иначе выведите $$$-1$$$.

Примеры
Входные данные
5
0 1 0 1 0
1 1 0 0 1
1 0 1 0 1
0 0 1 1 0
Выходные данные
5
Входные данные
3
1 0 0
0 0 0
0 0 0
0 0 0
Выходные данные
-1
Примечание

В первом примере из условия подойдет следующая последовательность обменов:

  • $$$(2, 1), (1, 1)$$$,
  • $$$(1, 2), (1, 3)$$$,
  • $$$(2, 2), (2, 3)$$$,
  • $$$(1, 4), (1, 5)$$$,
  • $$$(2, 5), (2, 4)$$$.

Можно показать, что меньшим числом обменов обойтись нельзя, поэтому ответ равен $$$5$$$.

Во втором примере из условия никакая последовательность ходов не приводит пазл к нужному виду. Следовательно, ответ $$$-1$$$.