# Naive Recursive coin change problem.

# Returns the count of ways we can sum
# S[0...m-1] coins to get sum n
def count(S, m, n):

    # If n is 0 then there is 1
    # solution (do not include any coin)
    if n == 0:
        return 1

    # If n is less than 0 then no
    # solution exists
    if n < 0:
        return 0

    # If there are no coins and n
    # is greater than 0, then no
    # solution exist
    if m <= 0 and n >= 1:
        return 0

    # count is sum of solutions (i)
    # including S[m-1] (ii) excluding S[m-1]
    return count(S, m - 1, n) + count(S, m, n - S[m - 1])


arr = [1, 2, 3]
m = len(arr)
print(count(arr, m, 4))


# Greedy
import sys

def get_change(m):
    if m == 0:
        return 0

    ans = []
    coins = [1,5,10]
    n = len(coins)
    i = n - 1
    while (i >= 0):
        while (m >= coins[i]):
            m -= coins[i]
            ans.append(coins[i])
        i -= 1

    return len(ans)

if __name__ == '__main__':
    m = int(sys.stdin.read())
    print(get_change(m))


# Dynamic Programming Coin Change
def count(S, m, n):
    # We need n+1 rows as the table is constructed
    # in bottom up manner using the base case 0 value
    # case (n = 0)
    table = [[0 for x in range(m)] for x in range(n + 1)]

    # Fill the entries for 0 value case (n = 0)
    for i in range(m):
        table[0][i] = 1

    # Fill rest of the table entries in bottom up manner
    for i in range(1, n + 1):
        for j in range(m):

            # Count of solutions including S[j]
            x = table[i - S[j]][j] if i - S[j] >= 0 else 0

            # Count of solutions excluding S[j]
            y = table[i][j - 1] if j >= 1 else 0

            # total count
            table[i][j] = x + y

    return table[n][m - 1]


arr = [1, 2, 3]
m = len(arr)
n = 4
print(count(arr, m, n))
