#include<bits/stdc++.h> #pragma GCC optimize("Ofast,O3,unroll-loops") using namespace std; #define pb emplace_back #define ALL(x) (x).begin(),(x).end() #define rALL(x) (x).rbegin(),(x).rend() #define srt(x) sort(ALL(x)) #define rev(x) reverse(ALL(x)) #define rsrt(x) sort(rALL(x)) #define sz(x) (int)(x.size()) #define aura 1e9 #define pii pair<int,int> void die(string s){ puts(s.c_str()); exit(0);} // #define int long long const int mod=1e9+7; int binpow(int a,int b) { int res=1; while(b) { if(b&1) res=res*a%mod; b>>=1; a=a*a%mod; } return res%mod; } int inv(int x) { return binpow(x,mod-2)%mod; } int memo[51][51][51][51]; void solve() { memset(memo,-1,sizeof(memo)); int n,m; cin>>n>>m; vector<vector<int>>a(n,vector<int>(m)); for(auto &x:a) for(int &y:x) cin>>y; int ans=0; vector<vector<int>>pref(n,vector<int>(m)); for(int i=0;i<n;++i) for(int j=0;j<m;++j) { pref[i][j]=a[i][j]; if(i) pref[i][j]+=pref[i-1][j]; if(j) pref[i][j]+=pref[i][j-1]; if(i && j) pref[i][j]-=pref[i-1][j-1]; } auto get=[&](int i1,int j1,int i2,int j2)->int { int cur=pref[i2][j2]; if(i1) cur-=pref[i1-1][j2]; if(j1) cur-=pref[i2][j1-1]; if(i1 && j1) cur+=pref[i1-1][j1-1]; return cur; }; auto rec=[&](auto rec,int x1, int y1,int x2,int y2)->int { if(x1==x2 && y1==y2) return 0; if(~memo[x1][y1][x2][y2]) return memo[x1][y1][x2][y2]; int sum=get(x1,y1,x2,y2); int mn=aura; for(int i=x1;i<x2;++i) mn=min(mn,rec(rec,x1,y1,i,y2)+rec(rec,i+1,y1,x2,y2)); for(int i=y1;i<y2;++i) mn=min(mn,rec(rec,x1,y1,x2,i)+rec(rec,x1,i+1,x2,y2)); memo[x1][y1][x2][y2]=mn+sum; return memo[x1][y1][x2][y2]; }; cout<<rec(rec,0,0,n-1,m-1)<<'\n'; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; #ifdef IOI freopen("test.in","r",stdin); freopen("test.out","w",stdout); #endif // cin>>t; while(t--) solve(); return 0; }