Problem
埃里克在大学担任保安，所以在一天的工作之后，他在大楼里走来走去，晚上关灯。
这栋楼有n层，左右各有两个楼梯。沿着连接左右楼梯的走廊，每层楼有m个房间。换句话说，建筑物可以表示为一个有 n 行和 m + 2 列的矩形，其中第一列和最后一列 —楼梯，中间有 m 根柱子——房间。
埃里克现在站在一楼左边的楼梯上。他想把所有地方的灯都关掉，而他又不想上到上面一层才把当前楼层的灯全部关掉。当然，Eric 必须在房间里才能关灯。埃里克花一分钟时间走上一层楼的楼梯，或者从同一层楼的隔壁房间或楼梯去隔壁房间/楼梯。关掉埃里克所在房间的灯并不花他的时间。
帮助 Eric 找到关闭建筑物中所有灯的最短时间。
请注意，埃里克不必回到原来的位置，也不需要访问已经熄灯的房间。
输入：
第一行包含两个整数 n 和 m (1 ≤ n ≤ 15, 1 ≤ m ≤ 100) —分别是楼层数和每层的房间数。
接下来的 n 行包含对建筑物的描述。每行包含一串长度为 m + 2 的 0 和 1，描述一个楼层（左边的楼梯，然后是 m 个房间，然后是右边的楼梯），其中 0 表示灯关闭，1 表示灯打开。楼层按从上到下的顺序给出，特别是最后一行描述了第一层。
每行的第一个和最后一个字符描述楼梯，因此它们始终为 0。
输出：
打印一个数字——关闭所有灯所需的最短时间。
示例：
<正文>
| 输入 |
输出 |
2 2
0010
0100 |
5 |
3 4
001000
000010
000010 |
12 |
说明：
第一个例子，Eric会先去一楼 1 房间，然后 —使用任何梯子到二楼的房间 2 。
第二个例子，他会先到一楼的第四个房间，右边楼梯上一层，进入二楼的第四个房间，再走右边的楼梯，到第二个最后一层的房间。