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

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 гривні, можна оплатити п’ятдесятигривневою, двадцятигривневою та двома двогривневими купюрами.