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

        #define ll long long
        #define pb push_back
        #define printV(v) for(int i=0;i<(int)v.size();i++){cout << v[i]<< " ";} cout << endl
        #define printRev(v) for(int i=(int)v.size()-1;i >= 0;i--){cout << v[i] << " ";} cout << endl
        #define sortV(v) sort(v.begin(),v.end())
        #define revV(v) reverse(v.begin(),v.end())
    

        ll a,b,c,d,e,f,g,n,m,k,t,x,h,w,p,q,y;
        string str = "";
        //ll mod = 1e9 + 7;
        ll mod = 998244353;
        const int N = 100009;
        
        
       
       void solve(){
            cin >> n >> m;
            if(m == 0){
                cout << "1\n";
                return;
            }else if(n == m){
                cout << "0\n";
                return;
            }
            vector<ll> v(m);
            for(int i=0;i  < m; i++){
                cin >> v[i];
            }
            sortV(v);
            v.push_back(n+1);
            vector<ll> distances;
            ll last = 0;
            ll mxLen = 0;
            ll mnLen = n;
            for(ll k : v){
                ll dis = k - last - 1;
                if(dis > 0){
                    mnLen = min(mnLen, dis);
                    mxLen = max(mxLen, dis);
                    distances.push_back(dis);
                }
                last = k;
            }
            ll answer = 0;
            for(ll k : distances){
                //cout << k  << " ";
                answer += (k/mnLen);
                if(k%mnLen) answer++;
            }
            cout << answer << endl;


       }
        


        int main(){
            ios_base::sync_with_stdio(false);
            
           


            int cases = 1;
           // cin >> cases;

            while(cases--) solve();
            return 0;

        }
#include <bits/stdc++.h>
using namespace std;
long long INF = 1000000000000000000;
int main(){
    string X;
    cin >> X;
    long long M;
    cin >> M;
    int N = X.size();
    int ma = 0;
    for(int i = 0; i < N; i++){
        ma = max(ma, (int)(X[i] - '0'));
    }
    if(N == 1){
        if(M < X[0] - '0') cout << 0 << endl;
        else cout << 1 << endl;
    }
    else{
        long long ub = INF + 1, lb = ma;
        while(ub - lb > 1){
            long long mid = (ub + lb) / 2;
            long long t = 1;
            long long sum = 0;
            int flag = 0;
            for(int i = N - 1; i >= 0; i--){
                sum += t * (X[i] - '0');
                if(sum > M){
                    flag = 1;
                    break;
                }
                if(i != 0 && (M - sum) / mid <  t){
                    flag = 1;
                    break;
                }
                t *= mid;
            }
            if(flag == 1) ub = mid;
            else lb = mid;
        }
        cout << lb - ma << endl;
    }
}