using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace NineCoins
{
    class Program
    {
        static void Main(string[] args)
        {
            decimal trials = 1000000;
            Random rnd = new Random();

            for (int n = 2; n<=9; n++)
            {
                List<int> allSums = new List<int>();

                for (int i = 0; i<trials; i++)
                {
                    List<int> coins = new List<int> { 1, 1, 5, 5, 10, 10, 25, 25, 25 };
                    int trialSum = 0;
                    for(int y = 0; y<n; y++)
                    {
                        int index = rnd.Next(0, coins.Count);
                        trialSum += coins[index];
                        coins.RemoveAt(index);
                    }
                    allSums.Add(trialSum);
                }

                IEnumerable<int> distinctSums = allSums.Distinct();
                int highestCount = 0;
                int mostCommonSum = 0;

                foreach(int sum in distinctSums)
                {
                    int count = allSums.Count(i => i == sum);
                    if (count > highestCount)
                    {
                        highestCount = count;
                        mostCommonSum = sum;
                    }
                }

                Console.WriteLine("Select {0}, Sum {1}", n, mostCommonSum);
            }
            Console.ReadKey();
        }
    }
}