#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int MAX_N = 1024;
const int MAX_LEN = 256;
const int base = 10000;
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 div(lnum X, int x) {
int i, t = 0;
for (i = X[0]; i > 0; --i) {
t = t * base + X[i];
X[i] = t / x;
}
while (X[0] > 1 && X[X[0]] == 0) --X[0];
}
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]);
}
char xxx[MAX_LEN];
sprintf(xxx, "%d", N);
carToLnum(xxx, T);
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);
mul(T, N - j + 1);
div(T, j);
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;
}