CF812B Sagheer, the Hausmeister

## 题目大意 有一栋楼房，里面有很多盏灯没关，为了节约用电 Sagheer 决定把这些灯都关了。 这楼有 $n$ 层，最左边和最右边有楼梯。每一层有 $m$ 个房间排成一排。这栋楼可以被表示成一个 $n$ 行 $m + 2$ 列的矩阵，其中每行第一个和最后一个格点表示楼梯，剩余 $m$ 个格点表示房间。 现在 Sagheer 在最底层的最左边楼梯，他想要关掉所有的灯。他每次可以走到相邻的房间，如果在楼梯口可以上下楼梯。他打算关掉所有开着的灯，在他没有将一层的所有灯都关闭前他不会上楼。现在求他最少需要走多少步可以关闭所有灯。 注意 Sagheer 不需要返回原处，最终可以停留在任意一个地方。

第一行包含两个整数 $n$ 和 $m$ $(1 \leq n \leq 15 , 1 \leq m \leq 100)$ — 表示层数和每层的房间数。 之后 $n$ 行描述这栋楼。每行包含一个长度为 $m + 2$ 的字符串表示这层楼的情况，如果值是 `1` 表示灯亮着，否则表示灯没亮。 保证每个字符串首尾位都为 `0`。

输出一个整数，表示熄灭所有灯所需的最少步数。

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.