Problem:
Problem G. Additions You are given an integer $N$ and a string consisting of ' + ' and digits. You are asked to transform the string into a valid formula whose calculation result is smaller than or equal to $N$ by modifying some characters. Here, you replace one character with another character any number of times, and the converted string should still consist of ' + ' and digits. Note that leading zeros and unary positive are prohibited. For instance, ' 0123+456 ' is assumed as invalid because leading zero is prohibited. Similarly, ' +1+2 ' and ' 2++3 ' are also invalid as they each contain a unary expression. On the other hand, ' 12345 ', ' 0+1+2 ' and ' 1234+0+0 ' are all valid. Your task is to find the minimum number of the replaced characters. If there is no way to make a valid formula smaller than or equal to $N$, output $-1$ instead of the number of the replaced characters. Input The input consists of a single test case in the following format. $N$
$S$ The first line contains an integer $N$, which is the upper limit of the formula ($1 \leq N \leq 10^9$). The second line contains a string $S$, which consists of ' + ' and digits and whose length is between $1$ and $1,000$, inclusive. Note that it is not guaranteed that initially $S$ is a valid formula. Output Output the minimized number of the replaced characters. If there is no way to replace, output $-1$ instead. Examples Sample Input 1 100
+123 Output for Sample Input 1 2 Sample Input 2 10
+123 Output for Sample Input 2 4 Sample Input 3 1
+123 Output for Sample Input 3 -1 Sample Input 4 10
++1+ Output for Sample Input 4 2 Sample Input 5 2000
1234++7890 Output for Sample Input 5 2 In the first example, you can modify the first two characters and make a formula ' 1+23 ', for instance. In the second example, you should make ' 0+10 ' or ' 10+0 ' by replacing all the characters. In the third example, you cannot make any valid formula less than or equal to $1$.

Solution (Python):
from heapq import heappush, heappop, heapify
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    N = int(readline())
    S = readline().strip()
    L = len(S)
    S += "+"
    if L % 2 == 0 and N < 10:
        write("-1\n")
        return
    pw10 = [1]*11
    for i in range(10):
        pw10[i+1] = pw10[i] * 10
    INF = N+1
    dist = [[INF]*(L+2) for i in range(L+1)]
    ques = [[] for i in range(L+1)]
    ques[0] = [(0, 0)]
    dist[0][0] = 0
    for k in range(L+1):
        que = ques[k]
        dist0 = dist[k]
        heapify(que)
        while que:
            cost, i = heappop(que)
            if dist0[i] < cost or i > L:
                continue

            p = S[i]
            if i+1 != L-1:
                if p != "+":
                    v = int(p)
                    if S[i+1] != '+':
                        if cost + v < dist[k+1][i+2]:
                            dist[k+1][i+2] = cost + v
                            ques[k+1].append((cost + v, i+2))
                    else:
                        if cost + v < dist0[i+2]:
                            dist0[i+2] = cost + v
                            heappush(que, (cost + v, i+2))
                if p != "0":
                    nk = k+1 + (S[i+1] != "+")
                    if cost < dist[nk][i+2]:
                        dist[nk][i+2] = cost
                        ques[nk].append((cost, i+2))
            def calc(c0, p):
                for j in range(i+2, min(i+10, L+1)):
                    if j == L-1:
                        continue
                    p1 = p + S[i+1:j]; l = j-i
                    c = c0 + p1.count("+")
                    v = int(p1.replace(*"+0"))
                    if v <= N:
                        nk = k+c + (S[j] != '+')
                        if cost + v < dist[nk][j+1]:
                            dist[nk][j+1] = cost + v
                            ques[nk].append((cost + v, j+1))
                    b = pw10[l-2]
                    for e in range(l-2, -1, -1):
                        a = (v // b) % 10
                        if a:
                            v -= a * b
                            c += 1
                            if v <= N:
                                nk = k+c + (S[j] != '+')
                                if cost + v < dist[nk][j+1]:
                                    dist[nk][j+1] = cost + v
                                    ques[nk].append((cost + v, j+1))
                        b //= 10
            if p not in "0+":
                calc(0, p)
            if p != "1":
                calc(1, "1")
        if dist0[L+1] <= N:
            write("%d\n" % k)
            break
solve()