フクイ国では,「フク」と呼ばれる通貨単位が用いられている. この国では1フク硬貨,10フク硬貨,40フク硬貨,50フク硬貨,200フク硬貨の5種類の硬貨が用いられている.
あたなは現在 N フクの現金を所持していて,全所持金を硬貨に両替しようとしている. 硬貨の合計枚数が最小になる方法で両替したときの,両替後の硬貨の枚数を出力するプログラムを作成せよ.
入力は以下の形式で与えれれる.
N
第1行目 N
は所持金額 N を与える.
1 ≤ N ≤ 107
硬貨の合計枚数が最小になる方法で両替したときの,両替後の硬貨の枚数を出力せよ.
入力1:
243
出力1:
5
243フクを硬貨の合計枚数が最小になるように両替すると,200フク硬貨1枚,40フク硬貨1枚,1フク硬貨3枚になる. したがって,両替後の硬貨の枚数は5枚である.
入力2:
485
出力2:
9