新版方格取数

【题目描述】

T博士的小儿子小T最近在玩一个游戏。 在一个$m$行$n$列的方格中有$m×n$个数，游戏规则如下： 先在方格边缘取走一个数，以此格为起点，下一步可向该格四个方向中未取数的方格前进，取走该方格的数并继续按如上规则取数。 如果某次取数恰好取到方格的边缘，则下一步可选择离开方格另取入口进入方格，当然也可以选择按上述规则取数。 游戏在小T取完方格内所有数或无法继续取方格内剩下的任何一个数的时候结束。 游戏有这样的得分规则：若方格内的某数$j$是方格内所有数中第$i$个取走的数，此次取数的得分为$i×j$。 小T最后的得分为游戏结束时他各次取数的得分之和。 小T想知道他所能取得的最大得分。 注意：已经取走数的方格不能再次取数或经过。

【输入】

第1行是两个正整数$m$和$n$，表示方格为$m$行$n$列。 第2到m+1行，每行为$n$个非负整数（注意可能为$0$），是方格里的数，保证这些数都小于$100000$。

【输出】

只要输出一行，为小T能取得的最大得分。

【输入样例】

3 3
1 2 3
8 9 4
7 6 5

【输出样例】

285

【提示】

【样例1解释】 依次取$1,2,3,4,5,6,7,8,9$ 【样例输入2】

3 3
0 0 0
0 1 0
0 0 0

【样例输出2】

9

【样例2解释】 周围绕一圈，第$9$次取$1$ 【数据规模】 对于50%的数据，满足$m×n≤9$。 对于100%的数据，满足$m×n≤16$。

3 3\n0 0 0\n0 1 0\n0 0 0

9