Description

题目背景

农夫琼斯有一个庄园农场，里面有着许多动物为他日夜劳作，而得到的只是刚好能果腹的食物，其余的收成都被农夫琼斯独吞。一头名叫老上校的年迈老猪意识到了动物被剥削的现状，为了鼓动动物们联合起来反抗农夫的剥削，他创作了《英格兰动物之歌》。老上校希望联合全英格兰的动物们共同反抗农夫，他派出了小马蓿苜向其他农场的动物传唱这首歌。

题目描述

小马蓿苜到另一个农场的地图可以看做一个N*M的网格图，左上角的坐标是(1,1)，右下角的坐标是(N,M)。小马蓿苜在左上角，另一个农场在右下角。这场革命刻不容缓，所以蓿苜只会选择最近的路到达另一个农场。而农夫们为了阻止动物的造反，早已在蓿苜到达其他农村的路上布下眼线，蓿苜希望走一条被观测度最小的路径。被观测度等于蓿苜在去农场的路径上可以看见蓿苜的不同眼线的数量，包括起点和终点。若蓿苜当前的位置为(x1,y1)，眼线可以看到蓿苜，当且仅当眼线的位置(x2,y2)满足|x1-x2|+|y1-y2|<=1。

Input Format

第一行包含两个整数，N和M。

接下来一个N*M的矩阵表示地图。其中Aij表示第i行第j列上眼线的数量。若Aij=0则表示当前位置上没有眼线，蓿苜的起点是第一行第一列，终点是第N行第M列，起点与终点也可能存在眼线。

Output Format

输出一个整数，表示最小的被观测度是多少。

Sample

样例输入

3 9
0 0 1 0 0 0 0 0 1
1 1 1 1 1 1 0 1 0
1 0 0 1 0 0 1 0 0

样例输出

9

Hint

样例说明

路径为

1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 1

可以看到它的眼线为

0 0 1 0 0 0 0 0 1
1 1 1 1 1 1 0 1 0

Hint