#include <stdio.h>
#define N 4


int maxPathSum(int tri[][N], int m)
{
	int i, j;
     
     for ( i=m-1; i>=0; i--)
     {
        for ( j=0; j<=i; j++)
        {
            if (tri[i+1][j] > tri[i+1][j+1])
                tri[i][j] += tri[i+1][j];
            else
                tri[i][j] += tri[i+1][j+1];
        }
     }
 
    
      
     return tri[0][0];   // return the top element which stores the maximum sum
}
 

int main()
{
   int tri[N][N] = {  {1,0,0,0},
                      {8,4,0,0},
                      {2,6,9,0},
					  {8,5,9,3}};
   printf("%d",maxPathSum(tri, 3));
   return 0;
}