#include<fstream>
#include<cstring>
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];
ifstream fin("bile2.in");
ofstream fout("bile2.out");
int verif(int a[], int poz){
    if(a[0] > poz){
        return 0;
    }
    else{
        return a[poz];
    }
}
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] = verif(a, i) + verif(b, i) + t;
        t = v[i] / 10;
        v[i] %= 10;
    }
    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] - verif(b, i) - t;
        if(v[i] < 0){
            v[i] += 10;
            t = 1;
        }
        else{
            t = 0;
        }
    }
    while(v[ v[0] ] == 0 && v[0] > 1){
        v[0]--;
    }
}
void mult(int a[], int b[], int c[]){
    c[0] = a[0] + b[0] - 1;
    int i, j, t = 0;
    for(i = 1; i <= c[0]; i++){
        c[i] = 0;
    }
    for(i = 1; i <= a[0]; i++){
        for(j = 1; j <= b[0]; j++){
            c[i + j - 1] += a[i] * b[j];
        }
    }
    for(i = 1; i <= c[0]; i++){
        c[i] += t;
        t = c[i] / 10;
        c[i] %= 10;
    }
    while(t != 0){
        c[++c[0]] = t % 10;
        t /= 10;
    }
}
void init(int a[]){
    fin>> sir + 1;
    a[0] = strlen(sir + 1);
    for(int i = 1; i <= a[0]; i++){
        a[i] = sir[ a[0] - i + 1] - '0';
    }
}
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++){
            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;
   d[0][0][0] = 1;
   d[0][0][1] = 0;
    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 = 0; j <= n; j++){
            if(j > dist){
                copiere(d[k][j], d[1 - k][j - dist - 1]);
            }
            else{
                d[k][j][0] = 1;
                d[k][j][1] = 0;
            }
            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;
}