#include <iostream>
#include <vector>
#include <string>
#include <limits>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);



/*
 * Complete the 'maxEnergy' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts 2D_INTEGER_ARRAY mat as parameter.
 */

void backtrack(vector<vector<int>> mat, int energy, int i, int j, int &maxi) {
    energy -= mat[i][j];
    
    if (energy < maxi) {
        return;
    }
    if (i == 3) {
        maxi = std::max(energy, maxi);
        return;
    }
    
    auto j_min = std::max(j - 1, 0);
    auto j_max = std::min(j + 1, 3);
    
    for (auto _j = j_min; _j <= j_max; ++_j) {
        backtrack(mat, energy, i + 1, _j, maxi);
    }
}

int maxEnergy(vector<vector<int>> mat) {
    int maxi = std::numeric_limits<int>::min();
    for (auto j = 0; j < mat[0].size(); ++j) {
        auto energy = 100;
        backtrack(mat, energy, 0, j, maxi);
    }
    return maxi;
}

int main()
{
    {
        vector<vector<int>> mat = {
            {99, 99, 0, 99},
            {99, 99, 0, 99},
            {99, 99, 0, 99},
            {99, 199, 116, 199}
        };

        assert(maxEnergy(mat) == -16);
    }

    return 0;
}