//Coded By Samet BELLUR

/*
If this problem was approached with a greedy approach, it could have been solved in the most data sets, but I used this way that
it would be able to reach the correct result in every dataset (greedy approch can not solve every data set with 100% accuracy). 
The cost is relatively higher, but it can calculate the highest total with 100% accuracy.

I used c # to solve this problem, the codes are below.
*/

//-------------------------------------------------------------|Main Clas|------------------------------------------------------
using System;
using System.IO;


namespace PyramidMaxSum
{
    class Program
    {
        static void Main(string[] args)
        {
            Pyramid pyramid = new Pyramid();

            string fileDes = "C:\\Users\\user\\Desktop\\pyramit.txt"; //file destination

            Node[] Pyramid = pyramid.BuildFromFile(fileDes);

            Console.WriteLine("\nMax Summary: {0}", pyramid.FindMaxSum(Pyramid));             
        }
    }
}

//-------------------------------------------------------------|Node Clas|-----------------------------------------------------

using System;
using System.Collections.Generic;
using System.Text;

namespace PyramidMaxSum
{
    public class Node
    {
        private int value;
        private int line;
        private int id;
        
        public Node(int value, int line, int id)
        {
            this.value = value;
            this.line = line;
            this.id = id;
        }
        
        public int Value
        {
            get { return value; }
            set { this.value = value; }
        }

        public int Line //The row with in the pyramid
        {
            get
            {
                return line;
            }
            set
            {
                line = value;
            }
        }

        public int Id //node id, used for display solution.
        {
            get
            {
                return id;
            }
            set
            {
                id = value;
            }
        }

        private Node downwardValue;
        public Node DownwardValue
        {
            get { return downwardValue; }
            set
            {
                downwardValue = value;
            }
        }

        private Node diagonalValue;
        public Node DiagonalValue
        {
            get { return diagonalValue; }
            set
            {
                diagonalValue = value;
            }
        }

        public Node getByMatrix (int position) //Returns a node at the desired position of a node (0 down, 1 diagonal)
        {
            if (position == 0)
            {
                return downwardValue;
            }
            else
            {
                return diagonalValue;
            }
        }
    }
}

//------------------------------------------------------------|Pyramid Clas|---------------------------------------------------

using System;
using System.Collections.Generic;
using System.IO;
using System.Text;

namespace PyramidMaxSum
{
    public class Pyramid
    {
        private int i;
        private int j;
        private int numberOfLines;
        public Node[] BuildFromFile(string fileDes)//Builds a pyramid using the tree structure.
        {
            StreamReader sr = new StreamReader(fileDes);

            //Assign number of lines from the file
            numberOfLines = File.ReadAllLines(fileDes).Length;
            string[] lines = new string[numberOfLines];

            //Read and assign lines to string array
            i = 0;
            while (sr.EndOfStream != true)
            {
                lines[i] = sr.ReadLine();
                i++;
            }

            //Start building a pyramid using a tree structure

            int[] allValues = new int[1];
            Node[] Pyramid = new Node[1];
            for (i = 0; i < numberOfLines; i++)                //This loop creates a array that consists of nodes.

            {                                                  //[0]         \
                string[] values = lines[i].Split(" ");         //[1] [2]      |->  Node[] Pyramid = {new Node(0)..}
                for (int j = 0; j < values.Length; j++)        //[3] [4] [5] /

                {                                              //Pyramid.txt -> Node Array
                    allValues[allValues.Length - 1] = Convert.ToInt32(values[j]);
                    Pyramid[Pyramid.Length - 1] = new Node(Convert.ToInt32(values[j]), i, Pyramid.Length - 1);

                    if (i == numberOfLines - 1 && j == values.Length - 1) {/*for the array does not expand in the last step*/}
                    else
                    {
                        Array.Resize(ref Pyramid, Pyramid.Length + 1);
                    }
                }
            }


            int pyramidIndex = 0;
            for (i = 0; i < numberOfLines; i++)                //This loop establishes connections between nodes.
                                                               //                                      / [0]         \
                                                               //                                     /  | \          \
            {                                                  //Node[] Pyramid = {new Node(0)..} -> |   [1]  [2]      | -> The Final Tree Structure in Memory.
                string[] lineValues = lines[i].Split(" ");     //                                     \  |  \ | \     /
                for (j = 0; j < lineValues.Length; j++)        // ("|" Downvard Connection)            \ [3] [4] [6] /
                {                                              // ("\" Diagonal Connection)
                    try
                    {
                        Pyramid[pyramidIndex].DownwardValue = Pyramid[pyramidIndex + (i + 1)];
                        Pyramid[pyramidIndex].DiagonalValue = Pyramid[pyramidIndex + (i + 2)];
                        pyramidIndex++;
                    }
                    catch (IndexOutOfRangeException)
                    {
                        break;
                    }

                }
            }

            // print pyramid
            Console.WriteLine("---------Pyramid----------");
            for (i = 0; i < numberOfLines; i++)
            {
                foreach (Node node in Pyramid)
                {
                    if (node.Line == i)
                    {
                        Console.Write(node.Value);
                        Console.Write(" ");
                    }
                }
                Console.Write("\n");
            }
            Console.Write("\n");

            return Pyramid;
        }


        public int FindMaxSum(Node[] Pyramid)
        {   //Calculation of the number of roads that can be traveled in the tree based on the number of lines in the pyramid.
            int Possibilities = Convert.ToInt32(Math.Pow(2, numberOfLines - 1)); //2^(numberOfLines-1) because no selection was made for the first node.
            int[] sum = new int[Possibilities]; //Keeping the sum of every possibility.

            int[,] choseMatrix = new int[Possibilities, numberOfLines - 1]; //Keeping selections for each possibility (0 = down, 1 = diagonal)

            for (i = 0; i < Possibilities; i++) //By converting all decimal numbers from 0 to the Possibilities number into their binary counterpart,             
            {                                   //we calculate all possible paths in the pyramid in 0 1 (down, diagonal) and assign them to a matrix.
                string binary = Convert.ToString(i, 2);
                for (j = 0; j < numberOfLines - 1; j++) //
                {
                    if (binary.Length < numberOfLines)
                    {
                        binary = binary.PadLeft(numberOfLines - 1, '0');
                    }
                    choseMatrix[i, j] = Convert.ToInt32(Char.GetNumericValue(binary[j]));
                }
            }
            //For example, if the pyramid has 3 rows; numberOfLines = 3 and the choseMatrix = int[4,2]
            //choseMatrix[0]= 0 toBinary = 0 0 (means down,down) | choseMatrix[1] = 1 toBinary = 0 1 (means down,diagonal)
            //choseMatrix[2]= 2 toBinary = 1 0 (means diagonal,down) | choseMatrix[3] = 3 toBinary = 1 1 (means diagonal,diagonal)

            Node startNode = Pyramid[0];
            int lineCutter = 0;
            int largestSum = 0;
            bool flag = true;

            while (flag) //Solution check
            {
                for (i = 0; i < Possibilities - lineCutter; i++) //Loop for all possibilities
                {
                    for (j = 0; j < numberOfLines - 1 - lineCutter; j++) //Loop for each line of possibilities. 
                    {
                        startNode = Rec(choseMatrix[i, j], startNode);
                        if (IsPrime(startNode.Value)) //Primality Test
                        {
                            sum[i] = 0; //If this possibility contains a prime number, the sum of this possibility is assigned to zero.
                            break;
                        }
                        sum[i] += startNode.Value;
                    }

                    if (largestSum < sum[i])//Finding largest sum
                    {
                        largestSum = sum[i];
                    }

                    startNode = Pyramid[0];
                }

                if (largestSum + Pyramid[0].Value != Pyramid[0].Value || numberOfLines - 1 - lineCutter == 1)
                {
                    flag = false; //Stops the while loop if a solution is found.
                }
                else
                {
                    lineCutter++; //If no solution is found, one of the lines is completely prime, so the bottom line is deleted and a solution is sought again.        
                }                 //This situation continues until a solution is found or until there are no lines other than the first line.
            }

            //Print Solve
            int solvePathIndex = 0;
            int lineIndex;
            for (i = 0; i < sum.Length; i++)
            {
                if (largestSum == sum[i])
                {
                    solvePathIndex = i;
                    break;
                }
            }
            startNode = Pyramid[0];
            Console.WriteLine("-------Solve PATH:-------");
            Console.Write("Line:{0} Index:{1} Value: {2}", Pyramid[0].Line, Pyramid[0].Id, Pyramid[0].Value);
            Console.Write("\n\n            |\n            V\n\n");

            if (largestSum + Pyramid[0].Value != Pyramid[0].Value)
            {
                for (j = 0; j < numberOfLines - 1 - lineCutter; j++)
                {
                    startNode = Rec(choseMatrix[solvePathIndex, j], startNode);
                    lineIndex = startNode.Id;
                    for (i = 0; i < startNode.Line; i++)
                    {
                        lineIndex -= i + 1;
                    }
                    Console.Write("Line:{0} Index:{1} Value: {2}", startNode.Line, lineIndex, startNode.Value);
                    Console.Write("\n\n            |\n            V\n\n");
                }
            }

            Console.WriteLine("---------Finish---------");
            return largestSum + Pyramid[0].Value;
        }

        public Node Rec(int position, Node start)//Returns a node at the desired position of a node (0 down, 1 diagonal)
        {
            return start.getByMatrix(position);
        }

        public bool IsPrime(int n) //Primality Test
        {
            if (n.Equals(2) || n.Equals(3)) { return true; }
            else if (n <= 1 || (n % 2).Equals(0) || (n % 3).Equals(0)) { return false; }

            int i = 5;
            while (Math.Pow(i, 2) <= n)
            {
                if ((n % i).Equals(0) || (n % (i + 2)).Equals(0)) { return false; }
                i += 6;
            }

            return true;
        }
    }
}