题目描述

一天小包同学利用 AI 元宇宙设备在湿地公园里探险玩挖金币游戏，湿地公园被划分为 $n \times m$ 个网格，每个格点内都有一座宫殿，每个宫殿都有一个数字，代表该宫殿内的金币，当小包同学第一次到达某个宫殿时就会拿走宫殿内的金币，并且该宫殿会沦陷消失不能再通过该点；当然有一些怪物会伪装成金币，踩到其退出游戏。通过搜集情报小包同学知道了怪物的伪装规则：怪物的数字会等于其相邻的上下左右四个宫殿数字的和。 已知当小包同学处在某个格点时，他只能移动到东南西北（或者说上下左右）四个方向之一的相邻格点上，小包同学想要活着从点 $A(1,1)$ 走到点 $B(n,m)$（均不为怪物），问在不走出湿地公园的情况下他最多能获得多少的金币？

输入格式

第一行为正整数 $n$ 和 $m$，代表湿地公园的大小；

接下来 $n$ 行，每行 $m$ 个数字代表每个宫殿内的数字；

输出格式

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

样例

输入数据#1

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  

输出数据#1

66

解释#1

经计算，样例中加粗标红的为怪兽，所以能经过最大的路径为 $1 \ 4 \ 8 \ 6 \ 10 \ 8 \ 5 \ 4 \ 4 \ 2 \ 2 \ 7 \ 1 \ 2 \ 2$，总和为 $66$。

数据范围

对于 $20\%$ 的数据：$n = m = 3$；

对于 $100\%$ 的数据：$1 \leq n, m < 8$，每个宫殿内的数字均为正整数且不超过 $10000$； 备注：官方题面描述数据范围有矛盾，且实际数据范围很小。