Prof. Vasechkin wants to represent positive integer *n* as a sum of addends, where each addends is an integer number containing only 1s. For example, he can represent 121 as 121=111+11+–1. Help him to find the least number of digits 1 in such sum.
The first line of the input contains integer *n* (1 ≤ *n* &lt; 10<sup class="upper-index">15</sup>).
def min_ones(n: int) -> int:
    # Initialize the array with base cases
    dp = [0, 1]
    # Loop through the array
    for i in range(2, n + 1):
        # Initialize the minimum number of digits 1 needed to represent i
        # as the maximum possible value
        dp.append(float("inf"))
        # Loop through all possible values of j
        for j in range(1, i + 1):
            # Check if j is an integer number containing only 1s
            if all(digit == "1" for digit in str(j)):
                # Update the minimum number of digits 1 needed to represent i
                dp[i] = min(dp[i], dp[i - j] + 1)
    # Return the minimum number of digits 1 needed to represent n
    return dp[n]

# Read the input
n = int(input())

# Print the minimum number of digits 1 needed to represent n
print(min_ones(n))
