AIOC Banner

Problem: Fashion Statement

Want to try solving this problem? You can submit your code online if you log in or register.


Fashion Statement

Input File: fashin.txt
Output File: fashout.txt
Time Limit: 1 second

In the latest trend of skin-tight jeans and slimline handbags, having a bulging wallet or purse is simply a fashion crime. You are faced with a dilemma: either you find yourself disowned by your fashion-conscious friends, or risk carrying too little money for your taxi ride home.

You wish to carry the exact amount of money for your taxi ride (in case you are mugged or otherwise lose it). However, you also wish to use as few notes as possible to avoid being ridiculed by your friends. The notes available to you come in denominations of $1, $5, $20 and $100 (you never carry coins, which are simply far too bulky).

For example, if your taxi fare costs $67, the smallest number of notes you can carry is six — this is achieved by carrying three $20 notes, one $5 note and two $1 notes (20+20+20+5+1+1 = 67).

Your task is to determine the smallest number of notes you need to carry in order to make up a given taxi fare.

Input

The input will consist of a single line containing the integer t, the cost of your taxi ride home. It is guaranteed that 0 <= t <= 1,000,000.

Output

Your output should consist of a single integer   the fewest number of notes required to make up your taxi fare.

Sample Input

67

Sample Output

6

Scoring

The score for each input file will be 100% if the correct answer is written to the output file and 0% otherwise.

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 24 May 2019,  4:06am AEST