In this solution, We don’t need the limitation \(a_{i,j} \le 300\).

First, we enumerate the left boundary and the right boundary of the rectangle. We call them \(l\) and \(r\). It costs \(O(M^2)\) time.

Now consider the following values:

• \(C_i\) = (the minimum value of line \(i\) in range \([l,r]\))

• \(D_i\) = (the sum of values of line \(i\) in range \([l,r]\))

They can be found in a total of \(O(N)\) time.

And now the problem has been turned into a new problem:

You are given two positive interger sequences \(C=(C_1,C_2,\dots,C_N)\) and \(D=(D_1,D_2,\dots,D_N)\) of length \(N\). Find the maximum possible value of \((\min_{i=l'}^{r'} C_i) +(\sum_{i=l'}^{r'}D_i)\) for all of ranges \([l',r']\) between \(1\) and \(N\).

It’s a classic problem. For each \(i\) between \(1\) and \(N\), we find the maximum range \([L_i,R_i]\) that satisfies \(L_i \le i \le R_i\) and \(\min_{j=L_i}^{R_i} C_j=C_i\). The answer to the problem is \(\max_{i=1}^{N}(C_i \times \sum_{j=L_i}^{R_i} D_j)\).

We could find the ranges with the help of a monotonic stack, and the total complexity is \(O(N)\).

Hence, the problem can be solved in a total of \(O(NM^2)\) time without the limitation \(a_{i,j} \le 300\).

• Sample Code (C++)

//A tree without skin will surely die.
//A man without face is invincible.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sqr(x) ((x)*(x))
#define all(x) (x).begin(),(x).end()
#define Tim ((double)clock()/CLOCKS_PER_SEC)
#define mid ((l+r)>>1)
#define lowbit(x) (x&-x)
int const N=3e2+10;
int a[N][N],c[N],d[N],l[N],r[N],s[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,m;cin>>n>>m;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j) cin>>a[i][j];
    int ans=0;
    for (int i=1;i<=m;++i){
        for (int k=1;k<=n;++k) d[k]=0,c[k]=1e9;
        for (int j=i;j<=m;++j){
            for (int k=1;k<=n;++k) d[k]+=a[k][j],c[k]=min(c[k],a[k][j]);
            for (int k=1;k<=n;++k) s[k]=s[k-1]+d[k];
            stack<int>ss;
            for (int k=1;k<=n;++k) l[k]=0,r[k]=n+1;
            for (int k=1;k<=n;++k){
                while (ss.size() && c[k]<c[ss.top()]) r[ss.top()]=k,ss.pop();
                ss.push(k);
            }
            while (ss.size()) ss.pop();
            for (int k=n;k>=1;--k){
                while (ss.size() && c[k]<c[ss.top()]) l[ss.top()]=k,ss.pop();
                ss.push(k);
            }
            for (int i=1;i<=n;++i) ++l[i],--r[i],ans=max(ans,c[i]*(s[r[i]]-s[l[i]-1]));
        }
    }
    cout<<ans<<'\n';
    return 0;
}