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