#include<bits/stdc++.h>
using namespace std;

#define long long int

signed main(){
    int a;
    cin >> a;

    int cnt = 0;
    int i = 1;

    while(1){
        if(i * 25 <= a)
        {
            cnt++;
            i++;
        }
        if(i * 25 > a){
            a -= (i - 1) * 25;
            break;
        }
    }

    i = 1;
    while(1){
        if(i * 10 <= a) 
        {
            cnt++;
            i++;
        }
        if(i * 10 > a)
            {
                a -= (i - 1) * 10;
                break;
            }
    }

    i = 1;
    while(1){
        if(i * 5 <= a)
        {
            cnt++;
            i++;
        }
    if(i * 5 > a){
        a -= (i - 1) * 5;
        break;
        }    
    }

    i = 1;
    while(1){
        if(i <= a){
            cnt++;
            i++;
        }
        if(i > a){
            a -= (i - 1);
            break;
        }
    }
    cout << cnt << endl;
}

### Prompt

Create a solution in cpp for the following problem:

You want to make change for $ n $ cents. Assuming that you have infinite supply of coins of 1, 5, 10 and / or 25 cents coins respectively, find the minimum number of coins you need.

Constraints

* $ 1 \ le n \ le 10 ^ 9 $

Input


$ n $


The integer $ n $ is given in a line.

output

Print the minimum number of coins you need in a line.

Examples

Input

100


Output

4


Input

54321


Output

2175

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;

#define long long int

signed main(){
    int a;
    cin >> a;

    int cnt = 0;
    int i = 1;

    while(1){
        if(i * 25 <= a)
        {
            cnt++;
            i++;
        }
        if(i * 25 > a){
            a -= (i - 1) * 25;
            break;
        }
    }

    i = 1;
    while(1){
        if(i * 10 <= a) 
        {
            cnt++;
            i++;
        }
        if(i * 10 > a)
            {
                a -= (i - 1) * 10;
                break;
            }
    }

    i = 1;
    while(1){
        if(i * 5 <= a)
        {
            cnt++;
            i++;
        }
    if(i * 5 > a){
        a -= (i - 1) * 5;
        break;
        }    
    }

    i = 1;
    while(1){
        if(i <= a){
            cnt++;
            i++;
        }
        if(i > a){
            a -= (i - 1);
            break;
        }
    }
    cout << cnt << endl;
}

```