#include <cstdio>
#include <algorithm>
using namespace std;
#define file_in "bile2.in"
#define file_out "bile2.out"
#define Baza 10000
#define Nmax 1020
char s[Nmax];
int comb[2][Nmax][Nmax/10];
int c[2][Nmax][Nmax/10];
int a[Nmax];
int b[Nmax];
int s1[Nmax];
int s2[Nmax];
int s3[Nmax];
//long long comb[1001][1001],a,b,c[1001][1001];
int n,d;
void add(int A[], int B[])
{
int i, t = 0;
for (i=1; i<=A[0] || i<=B[0] || t; i++, t/=Baza)
A[i] = (t += A[i] + B[i]) % Baza;
A[0]=i-1;
}
void mul(int A[], int B)
{
int i, t = 0;
for (i = 1; i <= A[0] || t; i++, t /= Baza)
A[i] = (t += A[i] * B) % Baza;
A[0] = i - 1;
}
void Mul(int A[], int B[])
{
int i, j, t, C[Nmax];
memset(C, 0, sizeof(C));
for (i = 1; i <= A[0]; i++)
{
for (t=0, j=1; j <= B[0] || t; j++, t/=Baza)
C[i+j-1]=(t+=C[i+j-1]+A[i]*B[j])%Baza;
if (i + j - 2 > C[0]) C[0] = i + j - 2;
}
memcpy(A, C, sizeof(C));
}
void sub(int A[], int B[])
{
int i, t = 0;
for (i = 1; i <= A[0]; i++)
A[i] += (t = (A[i] -= B[i] + t) < 0) * Baza;
for (; A[0] > 1 && !A[A[0]]; A[0]--);
}
void div(int A[], int B)
{
int i, t = 0;
for (i = A[0]; i > 0; i--, t %= B)
A[i] = (t = t * Baza+ A[i]) / B;
for (; A[0] > 1 && !A[A[0]]; A[0]--);
}
void init(int A[], int B)
{
do
{
A[++A[0]]=B%Baza;
B/=Baza;
}
while(B);
}
void print(int A[])
{
int i;
printf("%d",A[A[0]]);
for (i=A[0]-1;i>=1;--i)
printf("%.04d",A[i]);
}
int cmp(int A[], int B[])
{
int i;
if (A[0]>B[0])
return 1;
if (A[0]<B[0])
return -1;
for (i=A[0];i>=1;--i)
if (A[i]>B[i])
return 1;
else
if (A[i]<B[i])
return -1;
return 0;
}
int main()
{
int i,j,t,ind,stp,l;
freopen(file_in,"r",stdin);
freopen(file_out,"w",stdout);
scanf("%d %d\n", &n, &d);
scanf("%s\n", s);
l=strlen(s);
for (i=1;i<=l;i+=4)
{
++a[0];
for (j=3;j>=0;--j)
if (l-i-j>=0)
a[a[0]]=a[a[0]]*10+s[l-i-j]-'0';
}
scanf("%s\n", s);
l=strlen(s);
for (i=1;i<=l;i+=4)
{
++b[0];
for (j=3;j>=0;--j)
if (l-i-j>=0)
b[b[0]]=b[b[0]]*10+s[l-i-j]-'0';
}
memcpy(s3,b,sizeof(s3));
/* print(a);
printf("\n");
print(b);
printf("\n");*/
//merg cu comb
init(comb[0][0],1);
ind=1;
for (i=1;i<=n;++i,ind^=1)
{
memset(comb[ind],0,sizeof(comb[ind]));
init(comb[ind][0],1);
for (j=1;j<=n;++j)
{
add(comb[ind][j],comb[ind^1][j-1]);
add(comb[ind][j],comb[ind^1][j]);
}
}
stp=ind^1;
ind=1;
//merg cu c
for (i=0;i<=n;++i)
init(c[0][i],1);
for (i=1;i<=n;++i,ind^=1)
{
memset(c[ind],0,sizeof(c[ind]));
//init(c[ind][i],1);
for (j=1;j<=n;++j)
{
add(c[ind][j],c[ind][j-1]);
add(c[ind][j],c[ind^1][max(j-d-1,0)]);
}
//if (comb[n][i]*(b-a)>=b*c[i][n])
memcpy(s1,comb[stp][i],sizeof(s1));
memcpy(b,s3,sizeof(b));
sub(b,a);
Mul(s1,b);
memcpy(s2,c[ind][n],sizeof(s2));
Mul(s2,s3);
if (cmp(s1,s2)>=0)
{
printf("%d\n", i);
break;
}
}
fclose(stdin);
fclose(stdout);
return 0;
}