题目描述

某个街区是一个 $n\times m$ 的网格。坐标 $(i,j)$ 表示单元格位于第 $i$ 行，第 $j$ 列。每对相邻的单元格之间有一条道路连接，所有的道路都只能按规定的单一方向行驶。道路方向共有三种情况：

• 由单元格 $(i,j)$ 驶向单元格 $(i+1,j)$ ，$1\leq i<n$ ，方向向下；
• 由单元格 $(i,j)$ 驶向单元格 $(i,j+1)$ ，$1\leq j <m$ ，$i$ 是奇数，方向向右；
• 由单元格 $(i,j)$ 驶向单元格 $(i,j-1)$ ，$1<j\leq m$ ，$i$ 是偶数，方向向左。

每个单元格可能是商铺或者住宅，商铺用 $0$ 表示，住宅用 $1$ 表示。一个 $7\times 6$ 的街区示意图如下，空白单元格为商铺。配送公司需要用货车给每个住宅配送生活用品，货车从单元格 $(1,1)$ 出发，按道路规定方向行驶，从每一个单元格驶向其相邻的单元格均花费 $1$ 分钟。

请问货车最短需要行驶多少分钟才能完成配送任务？（忽略给每个住宅分配生活用品的时间，不考虑货车的回程）

输入格式

第 $1$ 行包含 $2$ 个整数 $n$ 和 $m$ ，表示行数和列数。

接下来 $n$ 行，每行包含 $m$ 个字符，由 $0$ 和 $1$ 组成，$0$ 代表该单元格为商铺，$1$ 代表该单元格为住宅。

保证单元格 $(1,1)$ 为商铺。

输出格式

输出 $1$ 行 $1$ 个整数，表示货车完成配送任务需要的最短时间（分钟）。

样例输入输出

7 6
010010
010100
001000
000010
000001
000000
100000

22

2 2
01
10

3

提示

样例1解释

数据范围

• 对于 $30\%$ 的数据， $1\leq n,m \leq 50$ ；
• 对于 $100\%$的数据， $1\leq n,m \leq 200$ 。