Всем известно, что ведьмак способен одолеть любых чудовищ, однако его услуги обойдутся недешево. К тому же ведьмак не принимает купюры, он принимает только чеканные монеты. В мире ведьмака существуют монеты с номиналами 1, 5, 10, 25.
Напишите программу, которая определяет, какое минимальное количество чеканных монет нужно заплатить ведьмаку.
На вход программе подается одно натуральное число - цена за услугу ведьмака.
Программа должна вывести минимально возможное количество чеканных монет для оплаты.
49
7
| # | Входные данные | Выходные данные |
|---|---|---|
| 1 | 49 | 7 |
| 2 | 1 | 1 |
| 3 | 5 | 1 |
| 4 | 10 | 1 |
| 5 | 25 | 1 |
| 6 | 2111 | 86 |
| 7 | 4 | 4 |
| 8 | 100 | 4 |
| 9 | 499 | 25 |
| 10 | 9 | 5 |