You have been given denomination of coins as 100, 50, 20, 10, 5, 2, and 1. It is desired to change the user inputted amount (AMT) using minimum number of coins. The logic to find out the minimum number of coins is to explore with highest denomination of coin first then second highest denomination and so on. You need to display the minimum number of coins needed to change the given amount. Example: if AMT is 269 then start exploring with Rs 100 coin and 2 coins of Rs. 100 are needed. Now balance amount is Rs 69, explore with Rs. 50 and 1 coin of Rs 50 is needed. Now balance amount is Rs 19, explore with Rs. 20 and 0 coin of Rs 20 is needed. Now balance amount is Rs 19, explore with Rs. 10 and 1 coin of Rs 10 is needed.Now balance amount is Rs 9, explore with Rs. 5 and 1 coin of Rs 5 is needed. Now balance amount is Rs 4, explore with Rs. 2 and 2 coins of Rs 2 is needed. Balance amount is Rs. 0 so AMT is changed with 2+1+0+1+1+2 = 7 coins. So display, 7.
Input Format
Input: An integer (representing the amount AMT).
Output Format
Output: An integer representing the minimum number of coins needed to change the input amount.
Constraints
NA
Example
Input
269
Output
7