У Аллена много денег, а именно, на счету в банке у него \(n\) долларов. По соображениям безопасности он хочет снять всю сумму наличными, мы не будет здесь описывать эти соображения. Номиналы долларовых купюр равны \(1\), \(5\), \(10\), \(20\), \(100\). Какое минимальное число купюр должен получить Аллен после того, как снимет все деньги?
Выходные данные
Выведите минимальное число купюр, которые должен получить Аллен.
Примечание
В первом примере Аллен может получить одну \(100\)-долларовую купюру, одну купюру в \(20\) долларов и одну купюру в \(5\) долларов. Нельзя получить \(125\) долларов с помощью одной или двух купюр.
Во втором примере Аллен может получить две \(20\)-долларовые купюры и три купюры в \(1\) доллар.
В третьем примере Аллен может снять \(100000000\) (десять миллионов!) \(100\)-долларовых купюр.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
125
|
3
|
|
2
|
43
|
5
|
|
3
|
1000000000
|
10000000
|