题目描述

Bessie不小心游荡出Farmer John的田地，而走进了相邻的农民的地。她举起一个木瓜，木瓜对奶牛来说可是不可多得得美味。

这个木瓜林像一般的威斯康星州的田地一样被分割成一个 $R$ 行 $C$ 列的网格( $1 \le R \le 40,1 \le C \le 40$ )。Bessie可以从一个格沿著一条跟 $X$ 轴或 $Y$ 轴平行的直线走到邻接的令一个格。Bessie发现一开始她自己在木瓜林的 $(1,1)$ ，也就是第一行第一列慢悠悠地咀嚼著木瓜。

Bessie总是用她最信赖地双筒望远镜去数每一个邻接的格的挂着的木瓜的数目。然后她就游荡到那个有最多没有被吃掉的木瓜的邻接的格子（保证这样的格子只有一个）。 按照这种移动方法，最终Bessie总是会在 $(R,C)$ 停止然后吃掉那裡的木瓜。

给定这个木瓜林的大小及每个格的木瓜数 $F$_$ij$ ($1 \le F$_$ij$$\le 100$), 要求Bessie一共吃了多少个木瓜。

输入

第 $1$ 行: 两个空格隔开的整数 $R$ 和 $C$ ；

第 $2$ 到 $R+1$ 行: 第 $i+1$ 行有 $C$ 个空格隔开的整数，表示第 $i$ 行的每个格的水果数。也就是 $F$_$i1$, $F$_$i2$, ..., $F$_$ic$。

输出

第一行: 一个单独的整数，表示到Bessie吃完右下角 $(R,C)$ 的木瓜回到牛棚的时候为止， 一共在木瓜林吃掉了多少个木瓜。

样例

3 4
3 3 4 5
4 5 3 2
1 7 4 2

39

来源

模拟