В банкомате имеется неограниченный запас купюр номиналами \(1, 5, 10, 50, 100, 500, 1000\) и \(5000\) рублей. Клиент хочет снять со счёта сумму в \(N\) рублей и получить её наличными.
Банкомат настроен так, чтобы выдавать клиенту как можно меньше купюр в сумме — это экономит физические купюры в кассете. Разумеется, выданные купюры должны в сумме составлять ровно \(N\) рублей.
Определите, какое минимальное количество купюр выдаст клиенту банкомат.
Формат входных данных
Одно целое число \(N\) (\(0 \le N \le 10^9\)) — сумма, которую нужно выдать.
Формат выходных данных
Одно целое число — минимальное количество купюр.
Примечание
В первом примере \(6250 = 5000 + 1000 + 100 + 100 + 50\) — итого 5 купюр.
Во втором примере \(N = 0\) — клиент снимает ноль рублей, купюр не нужно выдавать вообще.
| № | Входные данные | Выходные данные |
|
1
|
6250
|
5
|
|
2
|
0
|
0
|