#include <bits/stdc++.h>   using namespace std;   const int oo = (int)1e8;   vector<vector<int>> groupCosts;   vector<int> oldDP, newDP;   void solveDP(int L, int R, int L1, int R1) {     if (R < L) return;     int mid = (L + R) / 2;     int res = oo, pos = L1;     for (int i = L1; i <= min(mid, R1); i++) {       int now = groupCosts[i][mid];       int curCost = now + (i ? oldDP[i - 1] : 0);       if (curCost < res) {         res = curCost;         pos = i;       }     }     newDP[mid] = res;     solveDP(L, mid - 1, L1, pos);     solveDP(mid + 1, R, pos, R1);   }   void solve() {     int n, k;     cin >> n >> k;     vector<vector<int>> costs(n, vector<int>(n));     for (int i = 0; i < n; i++) {       for (int j = 0; j < n; j++) {         cin >> costs[i][j];         if (j) costs[i][j] += costs[i][j - 1];       }     }     groupCosts.resize(n, vector<int>(n));     for (int i = 0; i < n; i++) {       for (int j = i + 1; j < n; j++) {         groupCosts[i][j] += groupCosts[i][j - 1];         groupCosts[i][j] += costs[j][j - 1] - (i ? costs[j][i - 1] : 0);       }     }     oldDP.resize(n, oo);     newDP.resize(n, oo);     for (int curK = 0; curK < k; curK++) {       solveDP(curK, n - 1, 0, n - 1);       swap(oldDP, newDP);     }     cout << oldDP[n - 1] <<   n ;   }   int main() {     ios_base::sync_with_stdio(false);     cin.tie(NULL);     cout.tie(NULL);     solve();     return 0;   }   