题目描述

Bessie不小心游荡出Farmer John的田地，而走进了相邻的农民的地。她举起一个木瓜，木瓜对奶牛来说可是不可多得得美味。这个木瓜林像一般的威斯康星州的田地一样被分割成一个 $R$ 行 $C$ 列的网格($1 < = R < = 40, 1 < = C < = 40$)。Bessie可以从一个格沿著一条跟 $X$ 轴或 $Y$ 轴平行的直线走到邻接的另一个格。Bessie发现一开始她自己在木瓜林的$(1,1)$，也就是第 一行第一列慢悠悠地咀嚼著木瓜。 Bessie总是用她最信赖地双筒望远镜去数每一个邻接的格的低挂着的木瓜的数目。然后她就游荡到那个有最多没有被吃掉的木瓜的邻接的格子（保证这样的格子只有一个）。按照这种移动方法，最终Bessie总是会在$(R,C)$停止然后吃掉那里的木瓜。

给定这个木瓜林的大小及每个格的木瓜数 $F_{ij}(1 < = F_{ij} < = 100)$, 要求Bessie一共吃了多少个木瓜。

输入输出格式

输入

第一行: 两个空格隔开的整数 R 和 C.

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

输出

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

样例

输入1

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

输出1

39

时间及空间限制

1s, 256MB.

提示

Bessie按照下图数字旁边的字母的顺序吃掉木瓜。 (1,1) ---> (1,C) (1,1) 3a 3 4g 5h (1,C) | 4b 5c 3f 2i | (R,1) 1 7d 4e 2j (R,C) (R,1) ---> (R,C) 她吃了39个木瓜，剩下4个没有吃（也就是说除了2个格幸免於难，剩下的格子都被Bessie扫 荡过了）。

题目来源

USACO 2009 OCT