using System;

using System.Collections.Generic;

using System.IO;

using System.Linq;

​

​

namespace ConsoleApplication1

{

    public struct Node

    {

        public int Id;

        public int Value;

        public int ChildFirstId;

        public int ChildSecondId;

        public bool IsNull

        {

            get { return Value == 0; }

        }

​

        public bool IsPrime

        {

            get

            {

                if (Value < 2) return false;

                if (Value % 2 == 0) return (Value == 2);

                var root = (int)Math.Sqrt(Value);

                for (var i = 3; i <= root; i += 2)

                {

                    if (Value % i == 0) return false;

                }

                return true;

            }

        }

    }

​

    public class Program

    {

​

​

        private static readonly List<string> InputList = new List<string>()

        {

           "215",

            "193   124",

            "117   237   442",

            " 218   935   347   235",

            "320   804   522   417   345",

            "229   601   723   835   133   124",

            "248   202   277   433   207   263   257",

            "359   464   504   528   516   716   871   182",

            " 461   441   426   656   863   560   380   171   923",

            "381   348   573   533   447   632   387   176   975   449",

            "223   711   445   645   245   543   931   532   937   541   444",

            " 330   131   333   928   377   733   017   778   839   168   197   197",

            "131   171   522   137   217   224   291   413   528   520   227   229   928",

            "223   626   034   683   839    53   627   310   713   116   629   817   410   121",

            "924   622   911   233   325   139   721   218   253   223   528   233   230   124   233"

        };

​

        static int result;

        public static List<Node> Tree = new List<Node>();

​

        public void Main(string[] args)

        {

            var total = 0.0;

            for (var i = 0; i < 10; i++)

            {

                System.Diagnostics.Stopwatch myStopwatch = new System.Diagnostics.Stopwatch();

                myStopwatch.Start();

                // SetTreeFromFile();

                SetTreeFromArray(InputList);

                var node = Tree.FirstOrDefault(s => s.Id == 1);

                CountSummRecursive(node, node.Value);

                myStopwatch.Stop();

                total += myStopwatch.Elapsed.TotalSeconds;

                Console.WriteLine("The maximum sum:{0}, time: {1}", result, myStopwatch.Elapsed.TotalSeconds);

            }

            Console.WriteLine("The maximum sum: {0}, time:{1}", result, total / 100);

        }

​

        private static void CountSummRecursive(Node node, int sum)

        {

            var firstNode = Tree.FirstOrDefault(s => s.Id == node.ChildFirstId);

            if (!firstNode.IsNull && !firstNode.IsPrime)

                CountSummRecursive(firstNode, sum + firstNode.Value);

            else

                result = result > sum ? result : sum;

​

            var secondNode = Tree.FirstOrDefault(s => s.Id == node.ChildSecondId);

            if (!secondNode.IsPrime && !secondNode.IsNull)

                CountSummRecursive(secondNode, sum + secondNode.Value);

            else

                result = result > sum ? result : sum;

        }

​

        private static void SetTreeFromFile()

        {

            string line;

            var reader = new StreamReader(@"D:\input.txt");

            var lineId = 1;

            var nodeId = 1;

            while ((line = reader.ReadLine()) != null)

            {

                var linePieces = line.Split(' ').Where(x => !string.IsNullOrWhiteSpace(x)).Select(x => x).ToArray();

                foreach (string t in linePieces)

                {

                    if (!string.IsNullOrWhiteSpace(t))

                        Tree.Add(new Node

                        {

                            Id = nodeId,

                            Value = int.Parse(t),

                            ChildFirstId = nodeId + lineId,

                            ChildSecondId = nodeId + lineId + 1

                        });

​

                    nodeId++;

                }

                lineId++;

            }

            reader.Close();

        }

​

        private static void SetTreeFromArray(List<string> list)

        {

            var lineId = 1;

            var nodeId = 1;

            foreach (var line in list)

            {

                {

                    var linePieces = line.Split(' ').Where(x => !string.IsNullOrWhiteSpace(x)).Select(x => x).ToArray();

                    foreach (string t in linePieces)

                    {

                        if (!string.IsNullOrWhiteSpace(t))

                            Tree.Add(new Node

                            {

                                Id = nodeId,

                                Value = int.Parse(t),

                                ChildFirstId = nodeId + lineId,

                                ChildSecondId = nodeId + lineId + 1

                            });

​

                        nodeId++;

                    }

                    lineId++;

                }

            }

        }

    }

}