#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int MAX_N = 1024;
const int MAX_LEN = 300;
const int base = 10;
typedef int lnum[MAX_LEN];

void show(lnum X, FILE* f) {
    for (int i = X[0]; i > 0; --i) {
        fprintf(f, "%d", X[i]);
    }
    fprintf(f, "\n");
}

void carToLnum(char carX[MAX_LEN], lnum X) {
    int len = strlen(carX);
    memset(X, 0, sizeof(lnum));
    for (int i = len - 1; i >= 0; --i) {
        X[++X[0]] = carX[i] - '0';
    }
}

inline void one(lnum X) {
    memset(X, 0, sizeof(lnum));
    X[0] = X[1] = 1;
}

inline void add(lnum X, lnum Y) {
    int i, t = 0;
    for (i = 1; i <= X[0] || i <= Y[0] || t; ++i, t /= base) {
        X[i] = (t += (X[i] + Y[i])) % base;
    }
    X[0] = i - 1;
}

inline void sub(lnum X, lnum Y) {
    int i;
    for (i = 1; i <= X[0] || i <= Y[0]; ++i) {
        X[i] -= Y[i];
        if (X[i] < 0) {
            X[i] += base;
            X[i + 1] -= 1;
        }
    }
    while (X[0] > 1 && X[X[0]] == 0) --X[0];
}

inline void mul(lnum X, int x) {
    int i, t = 0;
    for (i = 1; i <= X[0] || t; ++i, t /= base) {
        X[i] = (t += (X[i] * x)) % base;
    }
    X[0] = i - 1;
}

inline void mul(lnum X, lnum Y) {
    lnum C;
    int i = 1, j = 1, t;
    memset(C, 0, sizeof(lnum));
    for (i = 1; i <= X[0]; ++i) {
        for (j = 1, t = 0; j <= Y[0] || t; ++j, t /= base) {
            C[i + j - 1] = (t += C[i + j - 1] + X[i] * Y[j]) % base;
        }
    }
    C[0] = i + j - 3;
    memcpy(X, C, sizeof(lnum));
}

inline int cmp(lnum X, lnum Y) {
    if (X[0] - Y[0]) {
        return X[0] - Y[0];
    }
    for (int i = X[0]; i > 0; --i) {
        if (X[i] - Y[i]) {
            return X[i] - Y[i];
        }
    }
    return 0;
}

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

inline void compute_comb(int n, int k, lnum X) {
    vector<int> wer;
    for (int i = k + 1; i <= n; ++i) wer.push_back(i);
    for (int i = 2; i <= n - k; ++i) {
        int x = i, d;
        for (int j = 0; j < (int) wer.size() || x > 1; ++j) {
            d = gcd(wer[j], x);
            x /= d, wer[j] /= d;
        }
    }
    memset(X, 0, sizeof(lnum));
    X[0] = X[1] = 1;
    for (int i = 0; i < (int) wer.size(); ++i) {
        mul(X, wer[i]);
    }
}

inline int compare(lnum X1, lnum Y1, lnum X2, lnum Y2) {
    lnum P1, P2;
    memcpy(P1, X1, sizeof(lnum));
    memcpy(P2, X2, sizeof(lnum));
    mul(P1, Y2);
    mul(P2, Y1);
    return cmp(P1, P2);
}

lnum C[2][MAX_N];
lnum S[2][MAX_N];

int N, D;
char carA[MAX_LEN], carB[MAX_LEN];
lnum A, B, T, W;

int main() {
    freopen("bile2.in", "rt", stdin);
    freopen("bile2.out", "wt", stdout);

    scanf("%d %d\n", &N, &D);
    scanf("%s\n%s\n", carA, carB);
    carToLnum(carA, A);
    carToLnum(carB, B);

    int prv = 0, nxt = 1;
    for (int i = 0; i < N; ++i)
        one(C[prv][i]);

    one(S[prv][0]);
    for (int i = 1; i < N; ++i) {
        one(S[prv][i]);
        add(S[prv][i], S[prv][i - 1]);
    }

    for (int j = 2; j <= N; ++j) {
        for (int i = 0; i <= D; ++i) {
            memset(C[nxt][i], 0, sizeof(lnum));
            memset(S[nxt][i], 0, sizeof(lnum));
        }

        for (int i = D + 1; i < N; ++i) {
            memcpy(C[nxt][i], S[prv][i - (D + 1)], sizeof(lnum));
            memcpy(S[nxt][i], S[nxt][i - 1], sizeof(lnum));
            add(S[nxt][i], C[nxt][i]);
        }

        compute_comb(N, j, T);
        memcpy(W, T, sizeof(lnum));
        sub(W, S[nxt][N - 1]);
        fprintf(stderr, "j = %d\n", j);
        show(T, stderr);
        show(W, stderr);


        if (compare(W, T, A, B) >= 0) {
            printf("%d\n", j);
            return 0;
        }

        swap(prv, nxt);
    }
    printf("%d\n", -47);
    return 0;
}