#2704. 旅游

题目描述

有一个N*M的格子地图，地图上的格子有些是障碍，不能通过，有些不是障碍，有一个快乐程度，从每个格子可以移向上下左右四个格子。

小月想从[1,1]格出发，旅游一些格子并回到[1,1]格，旅游的快乐程度等于经过的所有格子的快乐程度之和，小月想使得旅游的快乐程度之和尽可能大。

注意：

1.  保证[1,1]格不是障碍
   

2.  除[1,1]格外不能重复走过同一格
   

3.  [1,1]格的快乐程度只算一次
   

4.  快乐程度可能是负数
   

5.  若不能从[1,1]格出去并回来，则小月不会进行此次旅游。
   

6.  若旅游的快乐程度为负数，则小月不会进行此次旅游。
   

7.  若小月不会进行旅游，则旅游快乐程度为0。
   

输入格式

第一行两个正整数N，M。

接下来N行，每行M个整数，第i行第j列的数为a[i][j]。当a[i][j]=0时表示此格是障碍，否则表示快乐程度。

输出格式

仅一行一个数，表示最大的旅游快乐程度。

样例

样例输入

3 3  

1 9 -1  

-7 0 8  

-1 -1 -1  

样例输出

7

数据范围与提示

【数据规模和约定】

100%的数据中：N,M<=12,-10000<=a[i][j]<=10000。