#1767. 扩展最大子矩阵问题

扩展最大子矩阵问题

题目描述

魔法世界现在共有两套暗物质能量炮对抗修罗王的机器人军团,已知机器人军团在一 个n×m\red{n\times m}的二维矩阵中,请确定两个小的矩阵,使这两个矩阵中所有元素的总和最大,且 两个矩阵无公共元素。

输入格式

第一行为两整数n,m,\red{n,m,} 以下n\red{n}行,每行m\red{m}列,为矩阵中各元素的值。

输出格式

一个整数,即扩展最大子矩阵和。

样例

输入样例

3 3
1 2 3
1 -2 3
1 1 -1

输出样例

10