#include <bits/stdc++.h> #define int long long #define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0) using namespace std; int n,m,q[55][55],dp[55][55][55][55],x,mn,sum; signed main(void) { exoworldgd; cin >> n >> m, memset(dp,0,sizeof(dp)), memset(q,0,sizeof(q)); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> x, q[i][j] = (i>0?q[i-1][j]:0)+(j>0?q[i][j-1]:0)-(i>0&&j>0?q[i-1][j-1]:0)+x; for (int l1 = 1; l1 <= n; l1++) { for (int l2 = 1; l2 <= m; l2++) { for (int r1 = 0; r1+l1-1 < n; r1++) { for (int c1 = 0; c1+l2-1 < m; c1++) { if (l1 == 1 && l2 == 1) continue; mn = LLONG_MAX; for (int r = r1+1; r < r1+l1; r++) mn = min(mn,dp[r1][c1][r-1][c1+l2-1]+dp[r][c1][r1+l1-1][c1+l2-1]); for (int c = c1+1; c < c1+l2; c++) mn = min(mn,dp[r1][c1][r1+l1-1][c-1]+dp[r1][c][r1+l1-1][c1+l2-1]); sum = q[r1+l1-1][c1+l2-1]; if (r1 > 0) sum -= q[r1-1][c1+l2-1]; if (c1 > 0) sum -= q[r1+l1-1][c1-1]; if (r1 > 0 && c1 > 0) sum += q[r1-1][c1-1]; dp[r1][c1][r1+l1-1][c1+l2-1] = mn+sum; } } } } cout << dp[0][0][n-1][m-1]; }