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$.



Sample input:
100
+123


Sample output:
2

Submission status: Accepted

Solution code:
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()