题目描述

有一栋楼房，里面有很多盏灯没关，为了节约用电 Sagheer 决定把这些灯都关了。

这楼有 $n$ 层，最左边和最右边有楼梯。每一层有 $m$ 个房间排成一排。这栋楼可以被表示成一个 $n$ 行 $m + 2$ 列的矩阵，其中每行第一个和最后一个格点表示楼梯，剩余 $m$ 个格点表示房间。

现在 Sagheer 在最底层的最左边楼梯，他想要关掉所有的灯。他每次可以走到相邻的房间，如果在楼梯口可以上下楼梯。他打算关掉所有开着的灯，在他没有将一层的所有灯都关闭前他不会上楼。现在求他最少需要走多少步可以关闭所有灯。

注意 Sagheer 不需要返回原处，最终可以停留在任意一个地方。

输入格式

第一行包含两个整数 $n$ 和 $m\ (1 ≤ n ≤ 15$ 并且 $1 ≤ m ≤ 100)$ — 表示层数和每层的房间数。

之后 $n$ 行描述这栋楼。每行包含一个长度为 $m + 2$ 的字符串表示这层楼的情况，如果值是 $1$ 表示灯亮着，否则表示灯没亮。

保证每个字符串首尾位都为 $0$。

输出格式

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

2 2
0010
0100

5

3 4
001000
000010
000010

12

4 3
01110
01110
01110
01110

18