vector<vector<int>> prefSum;
vector<vector<int>> sufSum;
int n,m;
int getPrefixSum(int row, int left){
if(left==0)
return 0;
return prefSum[row][left-1];
}
int getSuffixSum(int row, int right){
if(right==0)
return 0;
return sufSum[row][right-1];
}
int solve(int row,int k, vector<vector<int>>& matrix){
if(k==0)
return 0;
if(row == n)
return -1e9;
int ans = -1;
for(int i=0;i<=min(m,k);i++){
for(int j=0;j<=i;j++){
int left = j;
int right = i-j;
ans = max(ans, getPrefixSum(row,left) + getSuffixSum(row,right) + solve(row + 1, k - i,matrix));
}
}
return ans;
}
int getMaximumSum(vector<vector<int>> matrix, int k) {
n = matrix.size();
m = matrix[0].size();
prefSum.resize(n, vector<int>(m,0));
sufSum.resize(n, vector<int>(m,0));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(j==0){
prefSum[i][j] = matrix[i][j];
}
else{
prefSum[i][j] = prefSum[i][j-1] + matrix[i][j];
}
}
}
for(int i=0;i<n;i++){
for(int j=m-1;j>=0;j--){
if(j==m-1){
sufSum[i][j] = matrix[i][j];
}
else{
sufSum[i][j] = sufSum[i][j+1] + matrix[i][j];
}
}
reverse(sufSum[i].begin(),sufSum[i].end());
}
return solve(0,k,matrix);
}