using System;
using System.Collections.Generic;
using System.Linq;

public class SumOfCoins
{
	public static void Main(string[] args)
	{
		var availableCoins = new[] { 1, 2, 5, 10, 20, 50 };
		var targetSum = 923;

		var selectedCoins = ChooseCoins(availableCoins, targetSum);

		Console.WriteLine($"Number of coins to take: {selectedCoins.Values.Sum()}");
		foreach (var selectedCoin in selectedCoins)
		{
			Console.WriteLine($"{selectedCoin.Value} coin(s) with value {selectedCoin.Key}");
		}
	}

	public static Dictionary<int, int> ChooseCoins(IList<int> coins, int targetSum)
	{
		var coinsDictionary = new Dictionary<int, int>();
		int sum = 0;
		coins = coins.OrderByDescending(x => x).ToList();

		for (int i = 0; i < coins.Count; i++)
		{
			while (sum + coins[i] <= targetSum)
			{
				sum += coins[i];
				if (!coinsDictionary.ContainsKey(coins[i]))
				{
					coinsDictionary.Add(coins[i], 0);
				}
				coinsDictionary[coins[i]]++;
			}
			if (sum == targetSum) break;
		}

		if (sum != targetSum)
		{
			Console.WriteLine("Error");
			Environment.Exit(0);
		}

		return coinsDictionary;
	}
}