E. Робот-пылесос
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим коридор, которой может быть представлен как матрица из $$$2$$$ строк и $$$n$$$ столбцов. Определим ячейку на пересечении $$$i$$$-й строки и $$$j$$$-го столбца как $$$(i, j)$$$. Расстояние между ячейками $$$(i_1, j_1)$$$ и $$$(i_2, j_2)$$$ равно $$$|i_1 - i_2| + |j_1 - j_2|$$$.

В клетке $$$(1, 1)$$$ стоит робот-пылесос. Некоторые клетки коридора чистые, остальные — грязные (клетка, в которой стоит робот, чистая). Вы хотите очистить коридор, поэтому вы планируете запустить робота для этой работы.

После запуска робот делает следующее. Пока есть хотя бы одна грязная клетка, робот выбирает ближайшую (к текущей клетке) клетку среди грязных, перемещается туда и очищает ее (клетка перестает быть грязной). После очистки робот снова находит ближайшую к его текущей клетке грязную клетку, и так далее. Этот процесс повторяется, пока весь коридор не станет чистым.

Однако в программе робота есть серьезная ошибка. Если в какой-то момент есть несколько ближайших (к текущей позиции робота) грязных клеток, то робот ломается.

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

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

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

В первой строке записано одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество столбцов в коридоре.

Затем следуют две строки, означающие $$$1$$$-ю и $$$2$$$-ю строку коридора. В этих строках по $$$n$$$ символов, где 0 означает чистую клетку, а 1 означает грязную клетку. Стартовая клетка робота $$$(1, 1)$$$ чистая.

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

Выведите одно целое число — максимально возможное количество клеток, которые можно оставить грязными, до запуска робота так, чтобы он не сломался.

Примеры
Входные данные
2
01
11
Выходные данные
2
Входные данные
2
01
01
Выходные данные
2
Входные данные
4
0101
1011
Выходные данные
4
Входные данные
4
0000
0000
Выходные данные
0
Входные данные
5
00011
10101
Выходные данные
4
Входные данные
6
011111
111111
Выходные данные
8
Входные данные
10
0101001010
1010100110
Выходные данные
6
Примечание

В первом примере можно очистить клетку $$$(1, 2)$$$, так что путь робота — $$$(1, 1) \rightarrow (2, 1) \rightarrow (2, 2)$$$.

Во втором примере можно оставить коридор как есть, так что путь робота — $$$(1, 1) \rightarrow (1, 2) \rightarrow (2, 2)$$$.

В третьем примере можно очистить клетку $$$(1, 2)$$$, так что путь робота — $$$(1, 1) \rightarrow (2, 1) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (1, 4)$$$.

В четвертом примере коридор уже чистый. Может, вы уже запускали робота?