Всем известно, что ведьмак способен одолеть любых чудовищ, однако его услуги обойдутся недешево. К тому же ведьмак не принимает купюры, он принимает только чеканные монеты. В мире ведьмака существуют монеты с номиналами 1, 5, 10, 25.
Напишите программу, которая определяет, какое минимальное количество чеканных монет нужно заплатить ведьмаку.
Формат входных данных
На вход программе подается одно натуральное число – цена за услугу ведьмака.
Формат выходных данных
Программа должна вывести минимально возможное количество чеканных монет для оплаты.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
49
|
7
|
|
2
|
1
|
1
|