/*
 * @author MUHAMMAD AZRI BIN JASNI @ ABDUL RANI
 * @version 4 APRIL 2013
 *
 * Reference : Muhammad Norzariman Bin Razari
 *           : http://code.jasonbhill.com/python/project-euler-problem-67/
 *              The sums traveling from top to bottom will be the same as the sums traveling from bottom to top. Start at the second to bottom row, and for each number N in that row, do the following: Take the maximum of the numbers directly down and left or down and right from N, and add that to N. Now do the same for the third-to-last row, then fourth-to-last, and so on. We’re modifying the triangle as we go to produce maximum partial sums from the bottom, and the last stage will be to replace to top number in the triangle, which will then be the maximum sum. So easy.
*/
import java.io.*;//File & BufferedReader
import java.util.*;//Scanner
public class solution67
{
    public static void main(String [] args) throws IOException
    {
        //time start
        long begin = System.currentTimeMillis();

        //get input
        //String inputFile = "testinput2.txt";
        String inputFile = "triangle.txt";
        Scanner sc = new Scanner(new FileReader(inputFile));
        ArrayList list = new ArrayList();

        while(sc.hasNext())
        {
            list.add(sc.nextInt());
        }
        //there seems to be waste of space, but I can't think of a way to look for size of the triangle.
        final int MAX = list.size();
        int triangle[][] = new int[MAX][MAX];
        for (int i=0, count=0; count<MAX;i++)
        {
            for (int j=0; j<=i&&count<MAX; j++)
            {
                triangle[i][j] = (int)list.get(count);
                count++;
            }
        }
        //display array
        /*for (int i=0; i<list.size(); i++)
        {
            for (int j=0; j<list.size(); j++)
            {   if(triangle[i][j]!=0)
                System.out.print(triangle[i][j]+" ");}
            System.out.println();
        }*/

        //perform the triangle max thingy

        for (int i=MAX-2; i>=0; i--)
        {
            for(int j=0; j<=i; j++)
            {
                //triangle[i][j] = triangle[i][j] + Math.max(triangle[i+1][j] , triangle[i+1][j+1]);
                triangle[i][j] += Math.max(triangle[i+1][j] , triangle[i+1][j+1]);
            }
        }
        //display final triangle as answer.
        System.out.println(triangle[0][0]);

        //time end
        long end = System.currentTimeMillis();
        System.out.println("Time:" + (end-begin)+" ms");
    }
}