import java.io.*;
public class OrthogonalTriangle {
    
     static int N = 3;
    
    static int maxPathSum(int tri[][], int m, int n) 
    { 
        for (int i = m - 1; i >= 0; i--) 
        { 
            for (int 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]; 
    } 
    public static void main (String[] args) 
    { 
        int tri[][] = { {1, 0, 0, 0}, 
                        {8, 4, 0, 0}, 
                        {2, 6, 9 , 0},
                        {5, 8, 9, 3}}; 
        System.out.println ( maxPathSum(tri, 3, 3)); 
    } 
}