C#でお釣り計算

先日ATMでお金を下ろしたら千円札が9枚も出て来まして…
ばっきゃろー！5000円ってもんを知らないのかっ！！って思いましてねｗ
前々から思ってましたけどその日はなんか許せなくて。プログラムにしちゃいました。

ただ、文字列使ったら面白くないじゃないですか。
1234.ToString()[0]とかしたら面白み全く無いですｗ
ってことでアルゴリズム部分に文字列を使うのは禁止ってことで。

問題をまとめると

• 入力された数値をお釣りとして計算する。
• 同じ硬貨や紙幣が重なる場合は一つ上の値段の硬貨や紙幣を使うこと。
• アルゴリズムに文字列の使用は禁止。
• お釣りは無制限にあるものとする（←制限つけようと思ったけどめんどくさくなった

私の解答はideone.comのこちからから。

もし皆さん回答作ったらコメントでもツイッターでもいいので教えてくれると私が楽しいです←