#include<fstream>
#include<cstring>
#define base 10000000
using namespace std;
int n, i, j, dist, k, k1;
char sir[100];
int a[500], b[500], sol1[500], sol2[500], aux[505];
int c[2][1005][500], d[2][1005][500], s[2][1005][500];
int pt[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000};
ifstream fin("bile2.in");
ofstream fout("bile2.out");
void adunare(int a[], int b[], int v[]){
    v[0] = max(a[0], b[0]);
    int i, t = 0;
    for(i = 1; i <= v[0]; i++){
        v[i] = a[i] + b[i] + t;
        t = v[i] / base;
        v[i] %= base;
    }
    if(t != 0){
        v[++v[0]] = t;
    }
}
void scadere(int a[], int b[], int v[]){
    v[0] = a[0];
    int i, t = 0;
    for(i = 1; i <= a[0]; i++){
        v[i] = a[i] - b[i] - t;
        if(v[i] < 0){
            v[i] += base;
            t = base;
        }
        else{
            t = 0;
        }
    }
    while(v[ v[0] ] == 0 && v[0] > 1){
        v[0]--;
    }
}
void mult(int a[], int b[], int c[]){
    long long d[500];
    d[0] = a[0] + b[0] - 1;
    int i, j, t = 0;
    for(i = 1; i <= d[0]; i++){
        d[i] = 0;
    }
    for(i = 1; i <= a[0]; i++){
        for(j = 1; j <= b[0]; j++){
            d[i + j - 1] += a[i] * 1LL * b[j];
        }
    }
    for(i = 1; i <= d[0]; i++){
        d[i] += t;
        t = d[i] / base;
        d[i] %= base;
    }
    while(t != 0){
        d[++d[0]] = t % base;
        t /= base;
    }
    for(i = 0; i <= d[0]; i++){
        c[i] = d[i];
    }
}
void init(int a[]){
    fin>> sir + 1;
    a[0] = 1;
    int m = strlen(sir + 1);
    int nrcif = 0;
    for(int i = m; i >= 1; i--){
        a[ a[0] ] = a[ a[0] ] + (sir[i] - '0') * pt[nrcif];
        nrcif++;
        if(a[ a[0] ] >= base){
            a[ ++a[0] ] = a[ a[0] - 1] / base;
            a[ a[0] - 1] %= base;
            nrcif = 1;
        }
    }
}
void copiere(int v[], int w[]){
    for(int i = 0; i <= w[0]; i++){
        v[i] = w[i];
    }
}
int compar(int v[], int w[]){
    if(v[0] != w[0]){
        if(v[0] > w[0]){
            return 1;
        }
        else{
            return 0;
        }
    }
    for(int i = v[0]; i >= 1; i--){
        if(v[i] < w[i]){
            return 0;
        }
        else{
            if(v[i] > w[i]){
                return 1;
            }
        }
    }
    return 1;
}
int main(){
    fin>> n >> dist;
    init(a);
    init(b);
    c[0][0][0] = c[0][0][1] = 1;
    k = 1;
    for(i = 1; i <= n; i++){
        c[k][0][0] = c[k][0][1] = 1;
        for(j = 1; j <= i; j++){
            memset(c[k][j], 0, sizeof(c[k][j]));
        }
        for(j = 1; j <= i; j++){
            adunare(c[1 - k][j - 1], c[1 - k][j], c[k][j]);
        }
        k = 1 - k;
    }
    k1 = 1 - k;
   // d[0][0][0] = d[0][0][1] = s[0][0][0] = s[0][0][1] = 1;
    for(i = 1; i <= n; i++){
        d[0][i][0] = d[0][i][1] = 1;
        adunare(d[0][i], d[0][i - 1], d[0][i]);
    }
    k = 1;
    for(i = 2; i <= n; i++){
        for(j = 1; j <= n; j++){
           // memset(s[k][j], 0, sizeof(s[k][j]));
            memset(d[k][j], 0, sizeof(d[k][j]));
        }
        for(j = 1; j <= n; j++){
            if(j > dist){
                copiere(d[k][j], d[1 - k][j - dist - 1]);
            }
            adunare(d[k][j - 1], d[k][j], d[k][j]);
        }
        scadere(c[k1][i], d[k][n], aux);
        mult(a, c[k1][i], sol1);
        mult(b, aux, sol2);
        if(compar(sol2, sol1)){
            fout<< i <<"\n";
            break;
        }
        k = 1 - k;
    }
    return 0;
}