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);
}
};
