Задача F. Бег по коридору ≡

Условие

Школьник Петя собрал собственный цветной дисплей с разрешением 2 пикселя по вертикали и N пикселей по горизонтали. Каждый пиксель определяется координатами (a, b), где a — номер строки от 1 до 2, а b — номер столбца от 1 до N.

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

В начале у игрока нулевой уровень усталости. Каждое перемещение добавляет к текущему уровню усталости единицу. Как только игрок перемещается на пиксель, занятый эликсиром, он выпивает эликсир, и уровень усталости уменьшается на единицу. Таким образом, перемещение на пиксель с эликсиром не увеличивает уровня усталости. Когда игрок покидает клетку, на которой был эликсир, она становится свободной.

Изначально игрок находится в пикселе с координатами (1, 1). Цель игры — добраться до N-ого столбца, минимизировав конечный уровень усталости.

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

Формат входного файла

В первой строке входного файла содержится число N — горизонтальное разрешение дисплея. Далее следует описание игрового поля — пара строк длиной N каждая. Символ "." (точка) соответствует свободному пикселю, символ "#" (решетка) — занятому препятствием, символ "X" (прописная латинская X) — пикселю с эликсиром.

Гарантируется, что первый символ первой строки равен ".", кроме того, последний символ хотя бы одной из двух строк не равен "#".

Гарантируется, что можно добраться до N-ого столбца.

Формат выходного файла

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

Ограничения

2 ≤ N ≤ 100

Примеры тестов

2
..
.#

1

6
....X.
#XXX..

3