まずは、次の問題について考えてみましょう。

高橋君は長さ \(N\) の整数列 \(A=(A _ 1,A _ 2,\ldots,A _ N)\) を持っています。この長さ \(1\) 以上の区間 \(\lbrack L,R\rbrack\) に対する \(A _ L+A _ {L+1}+\cdots+A _ R\) の最大値を求めてください。

この問題は、累積和を先頭から走査し、先頭からの min などを管理することで \(O(N)\) 時間で解くことができます（AWC0067 B なども参照してください）。

いま、\(\dfrac{M(M+1)}2\) 通りの \((c _ 1,c _ 2)\) の値を全探索することを考えます。 整数列 \(S=(S _ 1,S _ 2,\ldots,S _ N)\) を \[S _ i=A _ {i,c _ 1}+A _ {i,c _ 1+1}+\cdots+A _ {i,c _ 2}\] によって定めると、この \(S\) に対する上の問題の答えが \((c _ 1,c _ 2)\) を固定したときの元の問題の答えになっています。

あとは \(S\) の値を高速に求められればこの問題を解くことができます。 これは、\(A _ {i,j}\) の行ごとに累積和を求めておいたり、直前に探索した \((c _ 1,c _ 2)\) からの差分を計算するなどして \(O(M)\) 時間とできます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    vector A(N, vector<long>(M));
    for (vector<long>& v : A) {
        for (long& a : v) {
            cin >> a;
        }
    }

    // 横方向に累積和を取る
    for (vector<long>& v : A) {
        for (int i = 1; i < M; ++i) {
            v[i] += v[i - 1];
        }
        v.emplace(begin(v)); // 先頭に 0 を追加しておく
    }

    long ans = -10000; // 答えの下限は -10000
    for (long c1 = 0; c1 < M; ++c1) {
        for (long c2 = c1 + 1; c2 <= M; ++c2) { // (c1, c2) を全探索
            // S[i] := A[i][c2] - A[i][c1] に対して区間和の最大値を求める
            long prefix_min = 0, now = 0;
            for (int i = 0; i < N; ++i) {
                now += A[i][c2] - A[i][c1];
                ans = max(ans, now - prefix_min);
                prefix_min = min(prefix_min, now);
            }
        }
    }

    cout << ans << endl;
    return 0;
}

N, M = map(int, input().split())

A = [[0] + list(map(int, input().split())) for _ in range(N)]

# 横方向に累積和を取る
for v in A:
    for i in range(1, M + 1):
        v[i] += v[i - 1]

ans = -10000 # 答えの下限は -10000
for c1 in range(M):
    for c2 in range(c1 + 1, M + 1): # (c1, c2) を全探索
        # S[i] = A[i][c2] - A[i][c1] に対して区間和の最大値を求める
        prefix_min = 0
        now = 0
        for i in range(N):
            now += A[i][c2] - A[i][c1]
            ans = max(ans, now - prefix_min)
            prefix_min = min(prefix_min, now)

print(ans)