using System;

using System.Linq;

​

public class TrianglePathSum

{

     public static void Main()

    {

        int[][] triangle = new int[][]

        {

            new int[] { 1 },

            new int[] { 8, 4 },

            new int[] { 2, 6, 9 },

            new int[] { 8, 5, 9, 3 }

        };

​

        int maxSum = FindMaximumSum(triangle);

        Console.WriteLine($"Maximum sum: {maxSum}");

    }

    public static int FindMaximumSum(int[][] triangle)

    {

        if (triangle == null || triangle.Length == 0) return 0;

​

        int rows = triangle.Length;

        int[][] dp = new int[rows][];

​

        // Initialize dp array

        for (int i = 0; i < rows; i++)

        {

            dp[i] = new int[triangle[i].Length];

            Array.Fill(dp[i], int.MinValue);

        }

​

        // Initialize first row if it's not prime

        dp[0][0] = IsPrime(triangle[0][0]) ? int.MinValue : triangle[0][0];

​

        // Fill dp array

        for (int i = 0; i < rows - 1; i++)

        {

            for (int j = 0; j < triangle[i].Length; j++)

            {

                if (dp[i][j] == int.MinValue) continue;

​

                // check downward pAth

                if (!IsPrime(triangle[i + 1][j]))

                {

                    dp[i + 1][j] = Math.Max(dp[i + 1][j], 

                        dp[i][j] + triangle[i + 1][j]);

                }

​

                // check diagonal path

                if (!IsPrime(triangle[i + 1][j + 1]))

                {

                    dp[i + 1][j + 1] = Math.Max(dp[i + 1][j + 1], 

                        dp[i][j] + triangle[i + 1][j + 1]);

                }

            }

        }

​

        // find max value last row

        return dp[rows - 1].Max();

    }

    private static bool IsPrime(int number)

    {

        if (number < 2) return false;

        if (number == 2) return true;

        if (number % 2 == 0) return false;

​

        var boundary = (int)Math.Floor(Math.Sqrt(number));

​

        for (int i = 3; i <= boundary; i += 2)

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

​

        return true;

    }

​

}