Депутатські гроші

Обмеження: 2 сек., 256 МіБ

Часто-густо громадяни намагаються з’ясувати, наскільки багатими є депутати. Дехто вірить, що матеріальні статки окремих депутатів є необмеженими.

Тож уявіть собі депутата, у якого є необмежена кількість купюр усіх номіналів (1, 2, 5, 10, 20, 50, 100, 200 та 500 гривень). Він хоче придбати подарунок для своєї тещі, що коштує $n$ гривень.

Незважаючи на те, що наш герой-олігарх є нескінченно багатим, він також є нескінченно скупим та педантичним. Саме тому він хоче оплатити покупку готівкою без решти. Яка мінімальна кількість купюр йому для цього знадобиться?

Вхідні дані

У єдиному рядку задано одне натуральне число $n$ — вартість подарунку.

Вихідні дані

У єдиному рядку виведіть одне ціле число — мінімальну кількість купюр, що необхідна для покупки подарунка.

Обмеження

$1 \le n \le 10^9$.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
74	4

Примітки

Подарунок, що коштує 74 гривні, можна оплатити п’ятдесятигривневою, двадцятигривневою та двома двогривневими купюрами.