Allen has a LOT of money. He has n dollars in the bank. For security reasons, he wants to withdraw it in cash (we will not disclose the reasons here). The denominations for dollar bills are 1, 5, 10, 20, 100. What is the minimum number of bills Allen could receive after withdrawing his entire balance?

Input

The first and only line of input contains a single integer n (1 ≤ n ≤ 10^9).

Output

Output the minimum number of bills that Allen could receive.

Examples

Input

125


Output

3


Input

43


Output

5


Input

1000000000


Output

10000000

Note

In the first sample case, Allen can withdraw this with a 100 dollar bill, a 20 dollar bill, and a 5 dollar bill. There is no way for Allen to receive 125 dollars in one or two bills.

In the second sample case, Allen can withdraw two 20 dollar bills and three 1 dollar bills.

In the third sample case, Allen can withdraw 100000000 (ten million!) 100 dollar bills.
import sys,math
try:sys.stdin,sys.stdout=open('input.txt','r'),open('out.txt','w')
except:pass
from sys import stdin,stdout;mod=int(1e9 + 7);from statistics import mode
from collections import *;from math import ceil,floor,inf,factorial,gcd,log2,sqrt,log
ii1=lambda:int(stdin.readline().strip())
is1=lambda:stdin.readline().strip()
iia=lambda:list(map(int,stdin.readline().strip().split()))
isa=lambda:stdin.readline().strip().split()
# print('{:.3f}'.format(1),round(1.123456789,4))
# sys.setrecursionlimit(500000)
def lcm(a,b): return (a*b)//gcd(a,b)
def setbits(n):return bin(n).count('1')
def resetbits(n):return bin(n).count('0')
def modinv(n,p):return pow(n,p-2,p)
def ncr(n,r):
    num,den=1,1;r=min(n,n-r)
    for i in range(r):num*=(n-i);den*=(i+1)
    return num//den
def ncr_p(n, r, p):
    num,den=1,1;r=min(r,n-r)
    for i in range(r):num = (num * (n - i)) % p ;den = (den * (i + 1)) % p
    return (num * modinv(den,p)) % p
def isPrime(num) :
    if num<=1:return False
    if num==2 or n==3:return True
    if (num % 2 == 0 or num % 3 == 0) :return False
    m = int(num**0.5)+1
    for i in range(5,m,6):
        if (num % i == 0 or num % (i + 2) == 0) :return False
    return True
def bin_search(s, low, high, val):
    while low <= high:
        mid = low + (high - low) // 2;
        if s[mid] == val:return mid
        elif s[mid] < val:low = mid + 1
        else:high = mid - 1
    return -1
def sumofdigit(num):
    count=0;
    while num : count+=num % 10;num //= 10;
    return count;
def inputmatrix():
    r,c=iia();mat=[0]*r;
    for i in range(r):mat[i]=iia();
    return r,c,mat;
def prefix_sum(n,s):
    for i in range(1,n):s[i]+=s[i-1]
    return s;
def binomial(n, k):
    if 0 <= k <= n:
        ntok = 1;ktok = 1
        for t in range(1, min(k, n - k) + 1):ntok *= n;ktok *= t;n -= 1
        return ntok // ktok
    else:return 0
def divisors(n):
    res = [];
    for i in range(1,ceil(sqrt(n))+1):
        if n%i == 0:
            if i==n//i:res.append(i)
            else:res.append(i);res.append(n//i)
    return res;
def lcs(dp,s,n,p,m):
    for i in range(m+1):dp[0][i]=0
    for i in range(n+1):dp[i][0]=0
    for i in range(1,n+1):
        for j in range(1,m+1):
            if s[i-1]==p[j-1]:dp[i][j]=1+dp[i-1][j-1]
            else:dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    return dp[n][m]
# code here---
def lcs(dp,s,n,p,m):
    if n==0 or m==0:
        dp[n][m]=0
        return 0
    if dp[n][m]!=-1:return dp[n][m]
    if s[n-1]==p[m-1]:
        dp[n][m]=1+lcs(dp,s,n-1,p,m-1)
    else:
        dp[n][m]=max(lcs(dp,s,n-1,p,m),lcs(dp,s,n,p,m-1))
    return dp[n][m]
def lcs1(dp,s,n,p,m):
    for i in range(m+1):dp[0][i]=0
    for i in range(n+1):dp[i][0]=0
    for i in range(1,n+1):
        for j in range(1,m+1):
            if s[i-1]==p[j-1]:dp[i][j]=1+dp[i-1][j-1]
            else:dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    return dp[n][m]
# code here---
n = ii1();ans=0
for i in [100,20,10,5,1]:ans+=n//i;n=n%i;
print(ans)





