#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> cache(500);
vector<vector<int>> tri;

int dp(int n, int m)
{
    if(n==tri.size()-1) return cache[n][m] = tri[n][m];
    if(cache[n][m] != -1) return cache[n][m];
    return cache[n][m] = tri[n][m] + max(dp(n+1, m), dp(n+1, m+1));
}

int solution(vector<vector<int>> triangle) 
{
    for(int i=0; i<triangle.size(); i++)
        cache[i].assign(i+1, -1);
    tri = triangle;
    return dp(0,0);    
}