Light Change

Having saved up a collection of dollars ($1), quarters (25c), dimes (10c) and pennies (1c) in your piggy bank, you decide to treat yourself.

So off you went to the market, huffing and puffing. That piggy sure put on some weight. But soon you find something you want - a special edition millennium coin. Muhahaha, now you can get rid of all your pennies.

But the merchants don’t want all your pennies, they want the lightest change possible. Guess you won’t be able to get rid of all your pennies. But you still want that coin!

How can you pay using the fewest number of coins?

Input

A single integer $P$ ($1 \leq P \leq 1,000,000,000$), the price in cents.

Output

The minimum number of coins required.

Subtasks

• For 50% of points, $1 \leq P \leq 100$. (Note to new programmers: you can try calculating all answers by hand)
• For 25% of points, $1 \leq P \leq 100,000$.
• For the remaining 25% of points, $1 \leq P \leq 1,000,000,000$.