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

}