Background

DFS迷宫类

Description

一天 Watashi 在森林里探险挖金币，森林被划分为 n×m 个网格，每个格点内都有一座宫殿， 每个宫殿都有一个数字，代表该宫殿内的金币，当 Watashi 第一次到达某个宫殿时就会拿走宫殿内的金币，并且该宫殿会沦陷消失不能再通过该点；当然有一些怪物会伪装成金币夺取人类的性命。通过搜集情报 Watashi 知道了怪物的伪装规则：怪物的数字会等于其相邻的上下左右四个宫殿数字的和。 已知当 Watashi 处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Watashi 想要活着从点 A（1，1）走到点 B（n,m)（均不为怪物），问在不走出森林的情况下他最多能获得多少的金币?

Format

Input

第一行为正整数 n(1<=n<10)和 m(0<=m<10)，代表森林的大小；

接下来 N 行，每行 M 个数字代表每个宫殿内的数字；

Output

输出一行一个整数，代表 Watashi 获得的最大金币数。若 Watashi 不能活着走到 B 点请输出 -1。

Samples

5 5 
1 4 8 6 10 
3 1 4 5 8 
1 6 4 11 1 
2 0 2 1 2 
1 3 2 7 2

66

7 2 
5 19 
71 19 
5 56 
70 3 
41 9 
14 67 
7 1

387

Limitation

对于 100%的数据：0<=n,m<10；