Размен монетами

В обращении есть монеты достоинством 1, 2, 5, 10, 20, 50, 100, 200 и 500.

Наберите сумму $n$ наименьшим числом монет и выведите это число. Монет каждого вида сколько угодно.

Одно целое число $n$ от $1$ до $10^9$.

Одно число.

Для этого набора номиналов жадность верна: каждый следующий номинал делится на предыдущие достаточно удачно. Но проверять такое надо всегда — для набора 1, 3, 4 она уже ломается.