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

Input

100
+123


Output

2


Input

10
+123


Output

4


Input

1
+123


Output

-1


Input

10
++1+


Output

2


Input

2000
1234++7890


Output

2
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr ll inf = 2e9;

int main() {
    int n; cin >> n;
    string s; cin >> s;
    const int m = s.size();

    vector<vector<vector<ll>>> val(m, vector<vector<ll>>(10, vector<ll>(11, inf)));
    for(int i = 0; i < m; ++i) {
        for(int len = 0; len < 10; ++len) {
            if(i - len < 0) continue;
            auto t = s.substr(i - len, len + 1);
            int need = 0;
            for(int j = 0; j <= len; ++j) {
                if(j == 0) {
                    if((len != 0 && t[j] == '0') || !isdigit(t[j])) {
                        need += 1;
                        t[j] = len == 0 ? '0' : '1';
                    }
                } else {
                    if(!isdigit(t[j])) {
                        need += 1;
                        t[j] = '0';
                    }
                }
            }
            auto check =
                [&] (int p) {
                    return ((p == 0 && t[p] == (len == 0 ? '0' : '1')) || (p != 0 && t[p] == '0'));
                };
            int idx = 0;
            val[i][len][need] = stol(t);
            while(idx < (int)t.size()) {
                while(idx < (int)t.size() && check(idx)) idx++;
                if(idx < (int)t.size()) {
                    need += 1;
                    t[idx] = (len != 0 && idx == 0) ? '1' : '0';
                    val[i][len][need] = stol(t);
                }
                idx++;
            }
        }
    }
    //cout << val[9][9][10] << endl;
    // 0: => //, 1: => +
    vector<vector<vector<ll>>> dp(m + 1, vector<vector<ll>>(m + 1, vector<ll>(2, inf)));
    dp[0][0][1] = 0;
    for(int i = 0; i < m; ++i) {
        for(int cnt = 0; cnt <= m; ++cnt) {
            for(int pre = 0; pre <= 9; ++pre) {
                for(int x = 0; x <= pre + 1; ++x) {
                    if(i - pre < 0 || cnt + x > m) continue;
                    dp[i + 1][cnt + x][0] = min(dp[i + 1][cnt + x][0], dp[i - pre][cnt][1] + val[i][pre][x]);
                }
            }
            const int add = (s[i] != '+');
            if(cnt + add <= m) {
                dp[i + 1][cnt + add][1] = min(dp[i + 1][cnt + add][1], dp[i][cnt][0]);
            }
        }
    }
    ll ans = -1;
    for(int i = 0; i <= m; ++i) {
        if(dp[m][i][0] <= n) {
            ans = i;
            break;
        }
    }
    cout << ans << endl;
}

