CF812B.Sagheer, the Hausmeister

Some people leave the lights at their workplaces on when they leave that is a waste of resources. As a hausmeister of DHBW, Sagheer waits till all students and professors leave the university building, then goes and turns all the lights off.

The building consists of n floors with stairs at the left and the right sides. Each floor has m rooms on the same line with a corridor that connects the left and right stairs passing by all the rooms. In other words, the building can be represented as a rectangle with n rows and m + 2 columns, where the first and the last columns represent the stairs, and the m columns in the middle represent rooms.

Sagheer is standing at the ground floor at the left stairs. He wants to turn all the lights off in such a way that he will not go upstairs until all lights in the floor he is standing at are off. Of course, Sagheer must visit a room to turn the light there off. It takes one minute for Sagheer to go to the next floor using stairs or to move from the current room/stairs to a neighboring room/stairs on the same floor. It takes no time for him to switch the light off in the room he is currently standing in. Help Sagheer find the minimum total time to turn off all the lights.

Note that Sagheer does not have to go back to his starting position, and he does not have to visit rooms where the light is already switched off.

有些人离开工作场所时忘记关灯，这会造成资源浪费。作为杜伊斯堡-埃森应用技术大学（DHBW）的楼管员，Sagheer 会等到所有学生和教授都离开大学楼后，再前往各处将所有灯全部关闭。

该大楼共有 $n$ 层，每层左右两侧均设有楼梯。每层有 $m$ 个房间排成一行，一条走廊连接左右两侧楼梯，并依次经过所有房间。换言之，整栋楼可表示为一个 $n$ 行、$m+2$ 列的矩形网格：其中第 $1$ 列和第 $m+2$ 列代表楼梯，中间的 $m$ 列代表房间。

Sagheer 起始于底层（即第 $1$ 层）左侧楼梯处。他希望以如下方式关闭所有灯光：在他所处楼层的所有灯均被关闭之前，他不会走上更高一层。显然，Sagheer 必须亲自进入某个房间，才能将其灯关闭。Sagheer 每次使用楼梯上到下一层，或在同一楼层内从当前所在房间/楼梯移动至相邻的房间/楼梯，均需耗时 1 分钟；而他在当前所处房间内关闭灯光则不消耗时间。请帮助 Sagheer 计算关闭所有灯光所需的最少总时间。

注意：Sagheer 无需返回起始位置，也无需访问那些灯已处于关闭状态的房间。

The first line contains two integers n and m (1 ≤ n ≤ 15 and 1 ≤ m ≤ 100) — the number of floors and the number of rooms in each floor, respectively.

The next n lines contains the building description. Each line contains a binary string of length m + 2 representing a floor (the left stairs, then m rooms, then the right stairs) where 0 indicates that the light is off and 1 indicates that the light is on. The floors are listed from top to bottom, so that the last line represents the ground floor.

The first and last characters of each string represent the left and the right stairs, respectively, so they are always 0.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 15$，$1 \leq m \leq 100$），分别表示楼层数与每层的房间数。

接下来的 $n$ 行描述该建筑。每行是一个长度为 $m+2$ 的二进制字符串，表示一层楼（从左楼梯开始，接着是 $m$ 个房间，最后是右楼梯），其中 0 表示灯关闭，1 表示灯开启。楼层按从上到下的顺序给出，因此最后一行表示底层（地面层）。

每行字符串的第一个和最后一个字符分别表示左楼梯和右楼梯，因此它们始终为 0。

Print a single integer — the minimum total time needed to turn off all the lights.

输出一个整数——关闭所有灯所需的最少总时间。

In the first example, Sagheer will go to room 1 in the ground floor, then he will go to room 2 in the second floor using the left or right stairs.

In the second example, he will go to the fourth room in the ground floor, use right stairs, go to the fourth room in the second floor, use right stairs again, then go to the second room in the last floor.

In the third example, he will walk through the whole corridor alternating between the left and right stairs at each floor.

在第一个例子中，Sagheer 将先前往底层的 1 号房间，然后通过左侧或右侧的楼梯前往二层的 2 号房间。

在第二个例子中，他将先前往底层的 4 号房间，使用右侧楼梯前往二层的 4 号房间，再次使用右侧楼梯，最后前往顶层的 2 号房间。

在第三个例子中，他将走完整条走廊，并在每一层交替使用左侧和右侧的楼梯。