# work12
# 有一个由数字1，2，…，9组成的数字串，长度不超过200，
# 问如何将M（1≤M≤20）个加号插入这个数字串中，使得所形成的算法表达式的值最小。

def get_num(nums: list[int]) -> int:
    result = 0
    for num in list:
        result = result*10 + num
    return result

dp = []

def solve(nums: list, p: int, x: int) -> int:
    if dp[p][x] != -1:
        return dp[p][x]
    
    if x == 0:
        dp[p][0] = get_num(nums[0,p])
        return dp[p][0]
    
    for i in range(x, p-1, -1):
        dp[p][x] = min(dp[p][x], solve(i, x-1)+get_num(nums[i:p]))
    
    return dp[p][x]

result = solve([7,9,8,4,6], 5, 20)
print(result)