#include <cstddef>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <array>
#include <list>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <valarray>
#include <utility>
#include <tuple>
#include <cmath>
#include <memory>
#include <random>
#include <fstream>
#include <locale>
#include <regex>
#include <complex>

using ll = long long;
using ull = unsigned long long;
using ld = long double;

//vector
template <class T>
using vec = std::vector<T>;

template <class T>
using vvec = vec<vec<T>>;

constexpr std::size_t operator""_sz(ull n) { return std::size_t(n); }

constexpr int N = 8;

std::pair<int, vvec<bool>> solve(vvec<bool> map, int y, int x, int queenCount, vec<bool> h, vec<bool> w, vec<bool> tr, vec<bool> br)
{
    ++queenCount;

    map[y][x] = true;
    h[y] = true;
    w[x] = true;
    tr[y + x] = true;
    br[7 - y + x] = true;

    if (queenCount == N)
    {
        return make_pair(queenCount, map);
    }

    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
        {
            if (!h[i] && !w[j] && !tr[i + j] && !br[7 - i + j])
            {

                auto m = solve(map, i, j, queenCount, h, w, tr, br);

                if (m.first == N)
                {
                    queenCount = N;
                    map = m.second;
                    goto LOOP_END;
                }
            }
        }

LOOP_END:

    return make_pair(queenCount, map);
}

int main()
{
    using namespace std;
    // cerr.rdbuf(nullptr);

    int n;
    cin >> n;

    int ans{};

    vec<int> coins{ 25, 10 , 5, 1 };
    
    while (n > 0)
    {
        ++ans;
        for (auto c : coins)
        {
            if (n >= c)
            {
                n -= c;
                break;
            }
        }
    }

    cout << ans << endl;


    return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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 <cstddef>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <array>
#include <list>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <valarray>
#include <utility>
#include <tuple>
#include <cmath>
#include <memory>
#include <random>
#include <fstream>
#include <locale>
#include <regex>
#include <complex>

using ll = long long;
using ull = unsigned long long;
using ld = long double;

//vector
template <class T>
using vec = std::vector<T>;

template <class T>
using vvec = vec<vec<T>>;

constexpr std::size_t operator""_sz(ull n) { return std::size_t(n); }

constexpr int N = 8;

std::pair<int, vvec<bool>> solve(vvec<bool> map, int y, int x, int queenCount, vec<bool> h, vec<bool> w, vec<bool> tr, vec<bool> br)
{
    ++queenCount;

    map[y][x] = true;
    h[y] = true;
    w[x] = true;
    tr[y + x] = true;
    br[7 - y + x] = true;

    if (queenCount == N)
    {
        return make_pair(queenCount, map);
    }

    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
        {
            if (!h[i] && !w[j] && !tr[i + j] && !br[7 - i + j])
            {

                auto m = solve(map, i, j, queenCount, h, w, tr, br);

                if (m.first == N)
                {
                    queenCount = N;
                    map = m.second;
                    goto LOOP_END;
                }
            }
        }

LOOP_END:

    return make_pair(queenCount, map);
}

int main()
{
    using namespace std;
    // cerr.rdbuf(nullptr);

    int n;
    cin >> n;

    int ans{};

    vec<int> coins{ 25, 10 , 5, 1 };
    
    while (n > 0)
    {
        ++ans;
        for (auto c : coins)
        {
            if (n >= c)
            {
                n -= c;
                break;
            }
        }
    }

    cout << ans << endl;


    return 0;
}

```