题目描述

给定一个$n \times m$的网格，网格中有一些障碍物，求从左上角走到右下角最少经过多少次障碍物。

输入描述

第一行是两个整数$n,m$，表示有一个$n \times m$的网格。

接下来一行n个整数每行m个数，0表示无障碍，1表示有障碍。

保证 $1<n*m<100000$

输出描述

一行，一个整数，表示最近距离的最大值

样例

输入

3 3
0 1 0
0 1 1
0 1 0

输出

1