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

Limits: 2 sec., 256 MiB

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

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

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

Input

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

Output

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

Constraints

\(1 \le n \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
74	4

Notes

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