class SparseTable{ // https://github.com/ShahjalalShohag/code-library/blob/main/Data%20Structures/Sparse%20Table.cpp
public:
    int N;
    vector<vector<int>> t;
    SparseTable(int x) {
        x++;
        N = x;
        t.resize(x);
        for (int i = 0; i <x; i++) t[i].resize(32,0);
    }
    void build(int n, vector<int>& a) {
      for(int i = 1; i <= n; ++i) t[i][0] = a[i-1];
      for(int k = 1; k < 31; ++k) {
        for(int i = 1; i + (1 << k) - 1 <= n; ++i) {
          t[i][k] = max(t[i][k - 1], t[i + (1 << (k - 1))][k - 1]);
        }
      }
    }
    int query(int l, int r) {
        l++;
        r++;
      int k = 31 - __builtin_clz(r - l + 1);
      return max(t[l][k], t[r - (1 << k) + 1][k]);
    }
};
class Solution {
public:
    int N, M;
    long long inf = 1000000000000;
    long long dp[501][501] = {};
    long long pick (int pos, int a, int j, vector<SparseTable>& st) { // maximum value for third rook after first two are placed
        if(pos>=st.size()) return -inf;
        int ans = INT_MIN;
        if(j<a) swap(a,j);
        int a1 = 0, a2 = a-1, b1 = a+1, b2 = j-1, c1 = j+1, c2 = M-1;
        if(a1<=a2) {
            ans = max(ans, st[pos].query(a1, a2));
        }
        if(b1<=b2) {
            ans = max(ans, st[pos].query(b1, b2));
        }
        if(c1<=c2) {
            ans = max(ans, st[pos].query(c1, c2));
        }
        return ans;
    }
    long long dfs(int pos, int a, vector<vector<int>>& v, vector<SparseTable>& st) {
        if(pos>=v.size()) return -inf;
        if(dp[pos][a] != -1) return dp[pos][a];
        long long ans = dfs(pos+1,a,v,st);
        if (a==v[0].size()) { // place first rook
            for (int j = 0; j < v[pos].size(); j++) ans = max(ans, dfs(pos+1, j, v, st)+v[pos][j]);
        }
        else { // place second rook then find third rook position
            for (int j = 0; j < v[pos].size(); j++) {
                if(j==a) continue;
                ans = max(ans, pick(pos+1, a, j, st)+v[pos][j]);
            }
        }
        return dp[pos][a] = ans;
    }
    long long maximumValueSum(vector<vector<int>>& v) {
        N = v.size(), M = v[0].size();
        auto mx = v;
        memset(dp,-1, sizeof(dp));
        for (int j = 0; j < M; j++) {
            for (int i = N-2; i >= 0; i--) {
                mx[i][j] = max(mx[i][j], mx[i+1][j]);
            }   
        }
        vector<SparseTable> st(N, SparseTable(M));
        for (int i = 0; i < N; i++) {
            st[i].build(M,mx[i]);
        }
        return dfs(0, M, v, st);
    }
};

    long long pick (int pos, int a, int j, vector<SparseTable>& st) {
        if(pos>=st.size()) return -inf;
        int ans = INT_MIN;
        if(j<a) swap(a,j);
        int a1 = 0, a2 = a-1, b1 = a+1, b2 = j-1, c1 = j+1, c2 = M-1;
        if(a1<=a2) {
            ans = max(ans, st[pos].query(a1, a2));
        }
        if(b1<=b2) {
            ans = max(ans, st[pos].query(b1, b2));
        }
        if(c1<=c2) {
            ans = max(ans, st[pos].query(c1, c2));
        }
        return ans;
    }

    long long pick (int pos, int a, int j, vector<SparseTable>& st) {
        if(pos>=st.size()) return -inf;
        int ans = INT_MIN;
        if(j<a) swap(a,j);
        int a1 = 0, a2 = a-1, b1 = a+1, b2 = j-1, c1 = j+1, c2 = M-1;
        if(a1<=a2) {
            ans = max(ans, ans); // this doesn't do anything, just to illustrate the slowdown
        }
        if(b1<=b2) {
            ans = max(ans, ans);
        }
        if(c1<=c2) {
            ans = max(ans, ans);
        }
        return ans;
    }