You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

阿Q有一个神奇的矩阵，这个矩阵是环状的，它的第一行与最后一行相连，第一列与最后一列相连，即第一行的上一行为最后一行，最后一行的下一行为第一行，第一列的左一列为最后一列，最后一列的右一列为第一列。

他想知道这个矩阵的最大非空子矩阵和是多大，非空子矩阵指不为空且由相连的若干列和若干行组成的矩阵，原矩阵每个位置最多出现一次。

输入格式

第一行输入两个整数 n,m 代表矩阵的长和宽。$(1 \leq n,m \leq 90)$

接下来 n 行，每行 m 个整数，$a_{i1},a_{i2},a_{i3}\cdots a_{im}$，代表第 i 行的 m 个数。$(-10^9 \leq a_{ij} \le 10^9)$

输出格式

输出一个整数，代表这个环形矩阵的最大非空子矩阵和。

样例输入

3 3
1 -2 3
-4 5 -6
7 -8 9

样例输出

20