using System;

using System.Collections.Generic;

using System.Linq;

​

namespace NonPrimeTriangleMaxSum

{

    class Program

    {

        static void Main(string[] args)

        {

​

         var triangle = new List<int[]>

        {

            new int[] { 215 },

            new int[] { 193, 124 },

            new int[] { 117, 237, 442 },

            new int[] { 218, 935, 347, 235 },

            new int[] { 320, 804, 522, 417, 345 },

            new int[] { 229, 601, 723, 835, 133, 124 },

            new int[] { 248, 202, 277, 433, 207, 263, 257 },

            new int[] { 359, 464, 504, 528, 516, 716, 871, 182 },

            new int[] { 461, 441, 426, 656, 863, 560, 380, 171, 923 },

            new int[] { 381, 348, 573, 533, 447, 632, 387, 176, 975, 449 },

            new int[] { 223, 711, 445, 645, 245, 543, 931, 532, 937, 541, 444 },

            new int[] { 330, 131, 333, 928, 377, 733, 17, 778, 839, 168, 197, 197 },

            new int[] { 131, 171, 522, 137, 217, 224, 291, 413, 528, 520, 227, 229, 928 },

            new int[] { 223, 626, 34, 683, 839, 53, 627, 310, 713, 999, 629, 817, 410, 121 },

            new int[] { 924, 622, 911, 233, 325, 139, 721, 218, 253, 223, 107, 233, 230, 124, 233 }

        };

            int rowCount = triangle.Count;

            int[][] dp = new int[rowCount][];

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

            {

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

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

                {

                    dp[i][j] = int.MinValue; // başlangıçta ulaşılmaz olsun

                }

            }

​

            // İlk eleman eğer asal değilse dp[0][0] = triangle[0][0], yoksa ulaşılmaz

            if (!IsPrime(triangle[0][0]))

            {

                dp[0][0] = triangle[0][0];

            }

​

            // Üçgenin her satırı için hesaplama yapıyoruz

            for (int i = 1; i < rowCount; i++)

            {

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

                {

                    int currentValue = triangle[i][j];

                    // Eğer bu eleman asalsa buraya adım atılamaz, dp[i][j] = int.MinValue kalır

                    if (IsPrime(currentValue)) 

                        continue;

​

                    // Üstten aşağı (i-1, j) veya sol üstten diagonal (i-1, j-1) gelebiliriz

                    int fromAbove = int.MinValue;

                    int fromAboveLeft = int.MinValue;

​

                    // Üstten (i-1, j) gelme şartı: j üçgenin önceki satırında olmalı

                    if (j < dp[i - 1].Length && dp[i - 1][j] != int.MinValue)

                    {

                        fromAbove = dp[i - 1][j];

                    }

                    // Sol üstten diagonal (i-1, j-1) gelme şartı: j-1 >= 0 olmalı

                    if (j - 1 >= 0 && dp[i - 1][j - 1] != int.MinValue)

                    {

                        fromAboveLeft = dp[i - 1][j - 1];

                    }

​

                    int bestPrevious = Math.Max(fromAbove, fromAboveLeft);

​

                    if (bestPrevious != int.MinValue)

                    {

                        dp[i][j] = bestPrevious + currentValue;

                    }

                }

            }

​

            // Son satırda ulaşılabilir maksimum toplamı buluyoruz

            int maxSum = dp[rowCount - 1].Max();

​

            // Eğer maxSum halen int.MinValue ise demek ki yol yok (tamamen asallardan oluşmuş vb).

            if (maxSum == int.MinValue)

            {

                Console.WriteLine("Geçerli (asal olmayan) bir yol bulunamadı!");

            }

            else

            {

                Console.WriteLine($"Maksimum toplam: {maxSum}");

            }

        }

​

        /// <summary>

        /// Bir sayının asal olup olmadığını kontrol eden basit fonksiyon.

        /// 1 ve 0'ı burada asaldan saymıyoruz, dolayısıyla "non-prime" listesine dahil oluyorlar.

        /// </summary>

        static bool IsPrime(int number)

        {

            // Negatif sayılar, 0 veya 1 asla asal değildir.

            if (number < 2) return false;

​

            // 2 asaldır

            if (number == 2) return true;

​

            // Çift sayılar ve 2 dışında kalan negatifler asaldan çıkar

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

            // Kareköküne kadar kontrol et

            int limit = (int)Math.Sqrt(number);

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

            {

                if (number % i == 0)

                    return false;

            }

            return true;

        }

    }

}