#include <stdio.h>
#define N 1000
#define K 30
char a[N+1],b[N+1];
int c[N+1][N+1][K]={0},queue[N*N*K];
int max3(int a,int b,int c) { return a>b ? (a>c ? a : c) : (b>c ? b : c); };
void main()
{
int n,m,k, i,j,t;
int max;
freopen("input.txt","rt",stdin);
//freopen("output.txt","wt",stdout);
//input
scanf("%d",&k);
scanf("%d %s",&n,a);
scanf("%d %s",&m,b);
//dynamic
max=0;
for(i=n-1;i>=0;i--){
for(j=m-1;j>=0;j--){
c[i][j][k]=0;
if(a[i]==b[j]){
for(t=0;t<=k;t++){
if(c[i][j][k] <= c[i+1][j+1][t]) c[i][j][k] = c[i+1][j+1][t]+1;
} if(max < c[i][j][k]) max = c[i][j][k];
}
for(t=k-1;t>=0;t--){
c[i][j][t] = max3(c[i+1][j][t+1],c[i][j+1][t+1],c[i+1][j+1][t+1]);
}
}
}
printf("%d",max);
}