#define N 15
#include<stdio.h>
#include<math.h>
//input problem 18 datas
int dp[N][N];//memorized array for DP
int a[N][N] =
{
	{75,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
	{95,64,0,0,0,0,0,0,0,0,0,0,0,0,0},
	{17,47,82,0,0,0,0,0,0,0,0,0,0,0,0},
	{18,35,87,10,0,0,0,0,0,0,0,0,0,0,0},
	{20,4,82,47,65,0,0,0,0,0,0,0,0,0,0},
	{19,1,23,75,3,34,0,0,0,0,0,0,0,0,0},
	{88,2,77,73,7,63,67,0,0,0,0,0,0,0,0},
	{99,65,4,28,6,16,70,92,0,0,0,0,0,0,0},
	{41,41,26,56,83,40,80,70,33,0,0,0,0,0,0},
	{41,48,72,33,47,32,37,16,94,29,0,0,0,0,0},
	{53,71,44,65,25,43,91,52,97,51,14,0,0,0,0},
	{70,11,33,28,77,73,17,78,39,68,17,57,0,0,0},
	{91,71,52,38,17,14,91,43,58,50,27,29,48,0,0},
	{63,66,4,68,89,53,67,30,73,16,69,87,40,31,0},
	{4,62,98,27,23,9,70,98,73,93,38,53,60,4,23}
};

//return larger number a or b
int max(int a,int b)
{
		return (a > b) ? a : b;
}

int dfs(int i,int j,int sum)
{
	//before dp[i][j] memorized
	if(dp[i][j] == 0)
	{
		if(i==(N-1) || j == (N-1))
		{
			return sum;
		}
		else
		{
			sum = max(dfs(i+1,j,sum+a[i+1][j]),dfs(i+1,j+1,sum+a[i+1][j+1]));
		}
	dp[i][j]== sum;
	return sum;
	}
	//after dp[i][j] memorized
	else
	{
		return dp[i][j];
	}
}

int main()
{
	printf("max=%d\n",dfs(0,0,a[0][0]));
	return 0;
}