B. Охранник Сахир
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Некоторые люди не выключают свет, когда уходят из помещения, что ведет к бесполезной растрате энергии. Будучи охранником в университете, Сахир ждет, пока все студенты и профессора покинут здание, а затем идет и выключает везде свет.

В здании n этажей и две лестницы слева и справа. На каждом этаже есть m комнат вдоль коридора, который соединяет левую и правую лестницы. Другими словами, здание можно представить как прямоугольник из n строк и m + 2 столбцов, где первый и последний столбец  — лестницы, а m столбцов посередине — комнаты.

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

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

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

Первая строка содержит два целых числа n и m (1 ≤ n ≤ 15, 1 ≤ m ≤ 100) — количество этажей и количество комнат на каждом этаже, соответственно.

Следующие n строк содержат описание здания. Каждая строка содержит строку из нулей и единиц длины m + 2, описывающую один этаж (левую лестницу, затем m комнат, затем правую лестницу), где 0 означает, что свет выключен, а 1 означает, что свет включен. Этажи даны в порядке сверху вниз, в частности, последняя строка описывает первый этаж.

Первые и последние символы каждой строки описывают лестницы, поэтому они всегда равны 0.

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

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

Примеры
Входные данные
2 2
0010
0100
Выходные данные
5
Входные данные
3 4
001000
000010
000010
Выходные данные
12
Входные данные
4 3
01110
01110
01110
01110
Выходные данные
18
Примечание

В первом примере Сахир сначала пойдет в комнату 1 на первом этаже, а затем — в комнату 2 на втором этаже, используя любую лестницу.

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

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