[1932] 정수 삼각형

// 1932 정수 삼각형  
// 조합론, 파스칼의 삼각형  
#include<iostream>
#include<cstdio>
#include<string.h>
#define MAX 501
using namespace std;

int arr[MAX][MAX];
int dp[MAX][MAX];

int N;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	memset(arr, 0, MAX);
	memset(dp, 0, MAX);
	
    scanf("%d", &N);

    for(int i=1; i<=N; i++){
    	for(int j=1; j<=i; j++){
    		scanf("%d", &arr[i][j]);
		}
	}
    
	
    dp[1][1] = arr[1][1];
    dp[2][1] = dp[1][1] + arr[2][1];
    dp[2][2] = dp[1][1] + arr[2][2];
    for(int i=3; i<=N; i++){
		for(int j=1; j<=i; j++){
			dp[i][j] = arr[i][j] + max(dp[i-1][j-1], dp[i-1][j]);
		}
	}
	int res[N+1] = {};
	for(int i=1; i<=N; i++){
		res[i] = dp[N][i];
	}
	int ans = 0;
	for(int x: res){
			if(x > ans){
				ans = x;
			}
		}
	printf("%d", ans);
	
	return 0;
}