BOJ-1932

#include <iostream>
#include <algorithm>

using namespace std;

// int getMax(int a, int b) { return a > b ? a : b; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int n;
    int dp[500][500] = {0};

    cin >> n;
    if (n<1 || n>500) return 0;

    for (int i = 1; i < n; i++) 
        for (int j = 0; j <= i; j++) 
            cin >> dp[i][j];
     
    for (int i=1; i<n; i++) {
        for (int j=0; j<=i; j++) {
        if (j == 0) { 
            dp[i][j] += dp[i-1][j]; 
        } 
        else if (j == i) {
            dp[i][j] += dp[i-1][j-1];
        } 
        else {
            dp[i][j] = max(dp[i][j] + dp[i-1][j-1], dp[i][j] + dp[i-1][j]);
        }
    }

    int max = 0;
    for (int i=0; i<n; i++) {
	if (max < dp[n-1][i]) {
	    max = dp[n-1][i];
	}
    }
    cout << max << endl;
}