36

#include<stdio.h>
int arr[]={1,5,10,25,50};
int n=5,$;

int coinChange();

int main()
{
    while(scanf("%d",&$)!=EOF)
    {
        int answer=0;
        answer=coinChange();
        printf("%d\n",answer);
    }
    return 0;
}

int coinChange()
{
    int i,j,x,y;
    int TB[$+1][n];

    for(i=0;i<n;i++)
        TB[0][i]=1;

    for(i=1;i<=$;i++)
        for(j=0;j<n;j++)
        {
            if((i-arr[j])>=0)
                x=TB[i-arr[j]][j];
            else x=0;

            if(j>=1)
                y=TB[i][j-1];
            else y=0;

            TB[i][j]=x+y;
        }

    return TB[$][n-1];
}