using System;
using System.Collections.Generic;
using System.Linq;
 
class Program
{
    static void Main(string[] args)
    {
        double targetWeight = 23.7;
        var combinations = CoinCombination.GetCombinations(targetWeight);
 
        Console.WriteLine("Target Weight(Gram): " + targetWeight);
        Console.WriteLine("Number of Combinations: " + combinations.Count);
 
        Array.ForEach(Coin.Coins, x => Console.Write((x.Value + "yen").PadLeft(7)));
        Console.WriteLine(" : Total Amount");
        Console.WriteLine(new string('-', 58));
 
        foreach (var c in combinations)
        {
            foreach (var coin in Coin.Coins)
                Console.Write(c.GetCount(coin).ToString().PadLeft(7));
            Console.WriteLine(" : " + c.Value.ToString().PadLeft(12));
        }
    }
}
 
public struct Coin
{
    public int Value { get; private set; }
    public double Gram { get; private set; }
 
    // Gramの有効数字（小数点以下の桁数）
    public const int GramDecimals = 1;
 
    // 全硬貨のリスト（金額が小さい順）
    public static readonly Coin[] Coins 
        = new[] { new Coin(1, 1), new Coin(5, 3.7), new Coin(10, 4.5),
            new Coin(50, 4.0), new Coin(100, 4.8), new Coin(500, 7) };
 
    private Coin(int val, double gram) : this()
    {
        Value = val;
        Gram = Math.Round(gram, GramDecimals);
    }
 
    // 額面が同額以上のコインを返す
    public IEnumerable<Coin> GetMoreExpensiveOrEqual()
    {
        int index = Array.IndexOf(Coins, this);
        return Coins.Skip(index);
    }
}
 
public class CoinCombination
{
    public List<Coin> Coins { get; private set; }
 
    // この組み合わせの中の最高額の硬貨。(GetExpandeds参照)
    public Coin MostExpensive 
    { 
        get { return Coins[Coins.Count - 1]; }
    }
 
    private double mGram;
    public double Gram 
    {
        get { return mGram; }
        private set { mGram = Math.Round(value, Coin.GramDecimals); }
    }
 
    private int mValue = 0;
    public int Value
    {
        get 
        {
            if (mValue == 0) mValue = Coins.Sum((x) => x.Value);
            return mValue; 
        }
    }
 
    private CoinCombination() { Coins = new List<Coin>(); }
 
    public CoinCombination(params Coin[] coins) :this()
    {
        Coins.AddRange(coins);
        Gram = Coins.Sum(x => x.Gram);
    }
 
    // コインを一つ追加したCoinCombinationのリストを返す。
    // MostExpensiveより額面が小さいコインは追加しない。追加後のGramがmaxGramを超えるCoinCombinationは戻り値に含めない。
    private List<CoinCombination> GetExpandeds(double maxGram)
    {
        var ret = new List<CoinCombination>();
        foreach (var coin in MostExpensive.GetMoreExpensiveOrEqual())
        {
            var expanded = new CoinCombination() { Gram = this.Gram + coin.Gram };
            if(expanded.Gram <= maxGram)
            {
                expanded.Coins.AddRange(this.Coins); expanded.Coins.Add(coin);
                ret.Add(expanded);
            }
        }
        return ret;
    }
 
    // combinationsの要素とそれらに再帰的にコインを追加したものから
    // Gramの値がtargetGramに一致するものを検索しリストにして返す。
    private static List<CoinCombination> GetCombinations(double targetGram, IEnumerable<CoinCombination> combinations)
    {
        var ret = new List<CoinCombination>();
        foreach (var c in combinations)
        {
            if (c.Gram == targetGram)
                ret.Add(c);
            else
                ret.AddRange(GetCombinations(targetGram, c.GetExpandeds(targetGram)));
        }
        return ret;
    }
 
    public static List<CoinCombination> GetCombinations(double targetGram)
    {
        return GetCombinations(targetGram, Coin.Coins.Select(x => new CoinCombination(x)));
    }
 
    public int GetCount(Coin coin)
    {
        return Coins.Count(x => x.Value == coin.Value);
    }
}

dXNpbmcgU3lzdGVtOwp1c2luZyBTeXN0ZW0uQ29sbGVjdGlvbnMuR2VuZXJpYzsKdXNpbmcgU3lzdGVtLkxpbnE7CgpjbGFzcyBQcm9ncmFtCnsKICAgIHN0YXRpYyB2b2lkIE1haW4oc3RyaW5nW10gYXJncykKICAgIHsKICAgICAgICBkb3VibGUgdGFyZ2V0V2VpZ2h0ID0gMjMuNzsKICAgICAgICB2YXIgY29tYmluYXRpb25zID0gQ29pbkNvbWJpbmF0aW9uLkdldENvbWJpbmF0aW9ucyh0YXJnZXRXZWlnaHQpOwoKICAgICAgICBDb25zb2xlLldyaXRlTGluZSgiVGFyZ2V0IFdlaWdodChHcmFtKTogIiArIHRhcmdldFdlaWdodCk7CiAgICAgICAgQ29uc29sZS5Xcml0ZUxpbmUoIk51bWJlciBvZiBDb21iaW5hdGlvbnM6ICIgKyBjb21iaW5hdGlvbnMuQ291bnQpOwoKICAgICAgICBBcnJheS5Gb3JFYWNoKENvaW4uQ29pbnMsIHggPT4gQ29uc29sZS5Xcml0ZSgoeC5WYWx1ZSArICJ5ZW4iKS5QYWRMZWZ0KDcpKSk7CiAgICAgICAgQ29uc29sZS5Xcml0ZUxpbmUoIiA6IFRvdGFsIEFtb3VudCIpOwogICAgICAgIENvbnNvbGUuV3JpdGVMaW5lKG5ldyBzdHJpbmcoJy0nLCA1OCkpOwogICAgICAgICAgICAKICAgICAgICBmb3JlYWNoICh2YXIgYyBpbiBjb21iaW5hdGlvbnMpCiAgICAgICAgewogICAgICAgICAgICBmb3JlYWNoICh2YXIgY29pbiBpbiBDb2luLkNvaW5zKQogICAgICAgICAgICAgICAgQ29uc29sZS5Xcml0ZShjLkdldENvdW50KGNvaW4pLlRvU3RyaW5nKCkuUGFkTGVmdCg3KSk7CiAgICAgICAgICAgIENvbnNvbGUuV3JpdGVMaW5lKCIgOiAiICsgYy5WYWx1ZS5Ub1N0cmluZygpLlBhZExlZnQoMTIpKTsKICAgICAgICB9CiAgICB9Cn0KCnB1YmxpYyBzdHJ1Y3QgQ29pbgp7CiAgICBwdWJsaWMgaW50IFZhbHVlIHsgZ2V0OyBwcml2YXRlIHNldDsgfQogICAgcHVibGljIGRvdWJsZSBHcmFtIHsgZ2V0OyBwcml2YXRlIHNldDsgfQoKICAgIC8vIEdyYW3jga7mnInlirnmlbDlrZfvvIjlsI/mlbDngrnku6XkuIvjga7moYHmlbDvvIkKICAgIHB1YmxpYyBjb25zdCBpbnQgR3JhbURlY2ltYWxzID0gMTsKCiAgICAvLyDlhajnoazosqjjga7jg6rjgrnjg4jvvIjph5HpoY3jgYzlsI/jgZXjgYTpoIbvvIkKICAgIHB1YmxpYyBzdGF0aWMgcmVhZG9ubHkgQ29pbltdIENvaW5zIAogICAgICAgID0gbmV3W10geyBuZXcgQ29pbigxLCAxKSwgbmV3IENvaW4oNSwgMy43KSwgbmV3IENvaW4oMTAsIDQuNSksCiAgICAgICAgICAgIG5ldyBDb2luKDUwLCA0LjApLCBuZXcgQ29pbigxMDAsIDQuOCksIG5ldyBDb2luKDUwMCwgNykgfTsKCiAgICBwcml2YXRlIENvaW4oaW50IHZhbCwgZG91YmxlIGdyYW0pIDogdGhpcygpCiAgICB7CiAgICAgICAgVmFsdWUgPSB2YWw7CiAgICAgICAgR3JhbSA9IE1hdGguUm91bmQoZ3JhbSwgR3JhbURlY2ltYWxzKTsKICAgIH0KICAgICAgICAKICAgIC8vIOmhjemdouOBjOWQjOmhjeS7peS4iuOBruOCs+OCpOODs+OCkui/lOOBmQogICAgcHVibGljIElFbnVtZXJhYmxlPENvaW4+IEdldE1vcmVFeHBlbnNpdmVPckVxdWFsKCkKICAgIHsKICAgICAgICBpbnQgaW5kZXggPSBBcnJheS5JbmRleE9mKENvaW5zLCB0aGlzKTsKICAgICAgICByZXR1cm4gQ29pbnMuU2tpcChpbmRleCk7CiAgICB9Cn0KCnB1YmxpYyBjbGFzcyBDb2luQ29tYmluYXRpb24KewogICAgcHVibGljIExpc3Q8Q29pbj4gQ29pbnMgeyBnZXQ7IHByaXZhdGUgc2V0OyB9CgogICAgLy8g44GT44Gu57WE44G/5ZCI44KP44Gb44Gu5Lit44Gu5pyA6auY6aGN44Gu56Gs6LKo44CCKEdldEV4cGFuZGVkc+WPgueFpykKICAgIHB1YmxpYyBDb2luIE1vc3RFeHBlbnNpdmUgCiAgICB7IAogICAgICAgIGdldCB7IHJldHVybiBDb2luc1tDb2lucy5Db3VudCAtIDFdOyB9CiAgICB9CgogICAgcHJpdmF0ZSBkb3VibGUgbUdyYW07CiAgICBwdWJsaWMgZG91YmxlIEdyYW0gCiAgICB7CiAgICAgICAgZ2V0IHsgcmV0dXJuIG1HcmFtOyB9CiAgICAgICAgcHJpdmF0ZSBzZXQgeyBtR3JhbSA9IE1hdGguUm91bmQodmFsdWUsIENvaW4uR3JhbURlY2ltYWxzKTsgfQogICAgfQoKICAgIHByaXZhdGUgaW50IG1WYWx1ZSA9IDA7CiAgICBwdWJsaWMgaW50IFZhbHVlCiAgICB7CiAgICAgICAgZ2V0IAogICAgICAgIHsKICAgICAgICAgICAgaWYgKG1WYWx1ZSA9PSAwKSBtVmFsdWUgPSBDb2lucy5TdW0oKHgpID0+IHguVmFsdWUpOwogICAgICAgICAgICByZXR1cm4gbVZhbHVlOyAKICAgICAgICB9CiAgICB9CgogICAgcHJpdmF0ZSBDb2luQ29tYmluYXRpb24oKSB7IENvaW5zID0gbmV3IExpc3Q8Q29pbj4oKTsgfQoKICAgIHB1YmxpYyBDb2luQ29tYmluYXRpb24ocGFyYW1zIENvaW5bXSBjb2lucykgOnRoaXMoKQogICAgewogICAgICAgIENvaW5zLkFkZFJhbmdlKGNvaW5zKTsKICAgICAgICBHcmFtID0gQ29pbnMuU3VtKHggPT4geC5HcmFtKTsKICAgIH0KCiAgICAvLyDjgrPjgqTjg7PjgpLkuIDjgaTov73liqDjgZfjgZ9Db2luQ29tYmluYXRpb27jga7jg6rjgrnjg4jjgpLov5TjgZnjgIIKICAgIC8vIE1vc3RFeHBlbnNpdmXjgojjgorpoY3pnaLjgYzlsI/jgZXjgYTjgrPjgqTjg7Pjga/ov73liqDjgZfjgarjgYTjgILov73liqDlvozjga5HcmFt44GMbWF4R3JhbeOCkui2heOBiOOCi0NvaW5Db21iaW5hdGlvbuOBr+aIu+OCiuWApOOBq+WQq+OCgeOBquOBhOOAggogICAgcHJpdmF0ZSBMaXN0PENvaW5Db21iaW5hdGlvbj4gR2V0RXhwYW5kZWRzKGRvdWJsZSBtYXhHcmFtKQogICAgewogICAgICAgIHZhciByZXQgPSBuZXcgTGlzdDxDb2luQ29tYmluYXRpb24+KCk7CiAgICAgICAgZm9yZWFjaCAodmFyIGNvaW4gaW4gTW9zdEV4cGVuc2l2ZS5HZXRNb3JlRXhwZW5zaXZlT3JFcXVhbCgpKQogICAgICAgIHsKICAgICAgICAgICAgdmFyIGV4cGFuZGVkID0gbmV3IENvaW5Db21iaW5hdGlvbigpIHsgR3JhbSA9IHRoaXMuR3JhbSArIGNvaW4uR3JhbSB9OwogICAgICAgICAgICBpZihleHBhbmRlZC5HcmFtIDw9IG1heEdyYW0pCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGV4cGFuZGVkLkNvaW5zLkFkZFJhbmdlKHRoaXMuQ29pbnMpOyBleHBhbmRlZC5Db2lucy5BZGQoY29pbik7CiAgICAgICAgICAgICAgICByZXQuQWRkKGV4cGFuZGVkKTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICByZXR1cm4gcmV0OwogICAgfQoKICAgIC8vIGNvbWJpbmF0aW9uc+OBruimgee0oOOBqOOBneOCjOOCieOBq+WGjeW4sOeahOOBq+OCs+OCpOODs+OCkui/veWKoOOBl+OBn+OCguOBruOBi+OCiQogICAgLy8gR3JhbeOBruWApOOBjHRhcmdldEdyYW3jgavkuIDoh7TjgZnjgovjgoLjga7jgpLmpJzntKLjgZfjg6rjgrnjg4jjgavjgZfjgabov5TjgZnjgIIKICAgIHByaXZhdGUgc3RhdGljIExpc3Q8Q29pbkNvbWJpbmF0aW9uPiBHZXRDb21iaW5hdGlvbnMoZG91YmxlIHRhcmdldEdyYW0sIElFbnVtZXJhYmxlPENvaW5Db21iaW5hdGlvbj4gY29tYmluYXRpb25zKQogICAgewogICAgICAgIHZhciByZXQgPSBuZXcgTGlzdDxDb2luQ29tYmluYXRpb24+KCk7CiAgICAgICAgZm9yZWFjaCAodmFyIGMgaW4gY29tYmluYXRpb25zKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKGMuR3JhbSA9PSB0YXJnZXRHcmFtKQogICAgICAgICAgICAgICAgcmV0LkFkZChjKTsKICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgcmV0LkFkZFJhbmdlKEdldENvbWJpbmF0aW9ucyh0YXJnZXRHcmFtLCBjLkdldEV4cGFuZGVkcyh0YXJnZXRHcmFtKSkpOwogICAgICAgIH0KICAgICAgICByZXR1cm4gcmV0OwogICAgfQogICAgICAgIAogICAgcHVibGljIHN0YXRpYyBMaXN0PENvaW5Db21iaW5hdGlvbj4gR2V0Q29tYmluYXRpb25zKGRvdWJsZSB0YXJnZXRHcmFtKQogICAgewogICAgICAgIHJldHVybiBHZXRDb21iaW5hdGlvbnModGFyZ2V0R3JhbSwgQ29pbi5Db2lucy5TZWxlY3QoeCA9PiBuZXcgQ29pbkNvbWJpbmF0aW9uKHgpKSk7CiAgICB9CgogICAgcHVibGljIGludCBHZXRDb3VudChDb2luIGNvaW4pCiAgICB7CiAgICAgICAgcmV0dXJuIENvaW5zLkNvdW50KHggPT4geC5WYWx1ZSA9PSBjb2luLlZhbHVlKTsKICAgIH0KfQ==