Hit the Lottery

Problem statement

A prize desk pays winning tickets using banknotes of five fixed denominations: 1, 5, 10, 20 and 100. It has an unlimited supply of each denomination. Staff want to hand over the fewest notes possible while paying the exact prize amount, because smaller bundles are easier to verify and distribute. You are implementing the note-count calculation for the payment screen. Your task Given a positive integer amount n, determine the minimum number of banknotes whose values add up exactly to n. You may use any denomination multiple times. Return only the number of notes, not their individual values or the number of different denominations. Important details There is always a solution because denomination 1 is available. Do not round the amount or leave an unpaid remainder. A banknote worth 50 is not available in this exercise. Worked example For amount 137, use 100 + 20 + 10 + 5 + 1 + 1. This pays the prize with six notes.

Input format

One integer n.

Output format

Print the minimum banknote count.

Constraints

1 <= n <= 1000000000.

Sample input

137

Sample output

6