Deputy's Money

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian. In case of any discrepancy, the Ukrainian version is authoritative.

Quite often, citizens try to find out how wealthy deputies are. Some believe that the material wealth of certain deputies is unlimited.

So imagine a deputy who has an unlimited number of banknotes of all denominations (1, 2, 5, 10, 20, 50, 100, 200, and 500 hryvnias). He wants to buy a gift for his mother-in-law that costs \(n\) hryvnias.

Despite the fact that our oligarch hero is infinitely rich, he is also infinitely stingy and meticulous. That is why he wants to pay for the purchase in cash without getting any change. What is the minimum number of banknotes he will need for this?

Input

The single line contains a single natural number \(n\) — the cost of the gift.

Output

In the single line, output a single integer — the minimum number of banknotes required to purchase the gift.

Constraints

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

Samples

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

Notes

A gift costing 74 hryvnias can be paid for with a fifty-hryvnia, a twenty-hryvnia, and two two-hryvnia banknotes.