#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long 
#define vi vector < int > 
#define sz(a) ((int) (a).size())
#define ll long long 
#define ull unsigned long long
#define me(a, x) memset(a, x, sizeof(a)) 
using namespace std;
const int N = 2007;
ll cn, cm;
int n, m;
char s[N], t[N];
ll len[N], LST[N], pr[N];
mt19937_64 orz(time(0) ^ *new int);
int stk[N], tp;
void SLV() {
	L(j, 1, n) {
		char c = s[j];
		int mp = 1;
		L(i, 1, m) if(len[i] >= len[mp]) mp = i;
		int k = mp, lst = -1;
		tp = 0;
		R(o, m, 1) {
			if(k <= 0) k += m;
			if(t[k] == c) {
				while(tp) {
					int cur = stk[tp], add = cur < k;
					if(len[cur] > len[k] + add) swap(len[cur], len[k]), len[cur] += add, len[k] -= add;
					--tp; 
				}
				lst = k;
			} 
			while(tp && make_pair(len[stk[tp]], stk[tp]) < make_pair(len[k], k)) --tp;
			stk[++tp] = k;
			--k;
		}
		if(lst > 0) len[lst] += 1;
//		L(i, 1, m) {
//			cout << len[i] << ' ';
//		}
//		cout << endl;
	}
}
ull hsh[N], F[N]; 
int W[N][N];

inline int getans() {
	int N = n * cn;
	int M = m * cm; 
	vector < char > S(N + 1), T(M + 1);
	L(i, 1, n) S[i] = s[i];
	L(i, 1, m) T[i] = t[i];
	L(i, n + 1, N) S[i] = S[i - n];
	L(i, m + 1, M) T[i] = T[i - m];
	vector < vi > dp(N + 1, vi(M + 1));
	L(i, 1, N) {
		L(j, 1, M) {
			dp[i][j] = max(dp[i - 1][j - 1] + (S[i] == T[j]), max(dp[i - 1][j], dp[i][j - 1]));
		}
	}
	return dp[N][M];
}
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
//	cn = cm = 100;
//	n = m = 10;
//	L(i, 1, n) s[i] = orz() % 3 + 'A';
//	L(i, 1, m) t[i] = orz() % 3 + 'A';
//	cout << n << ' ' << m << ' ' << (s + 1) << ' '<< (t + 1) << endl;
//	cout << getans() << endl;
	cin >> cn >> cm;
	cin >> (s + 1) >> (t + 1);
	n = strlen(s + 1);
	m = strlen(t + 1);
	int cnt = min(1000LL, cn);
	L(o, 1, cnt) SLV();
	cn -= cnt, cnt = min(1000LL, cn);
	L(i, 1, m) pr[i] = len[i];
	L(o, 1, cnt) {
		L(i, 1, m) LST[i] = len[i];
		SLV();
		L(i, 1, m) W[o][i] = len[i] - LST[i];
	}
	L(i, 1, m) len[i] = pr[i];
	L(i, 1, m) {
	
	L(j, 1, cnt) F[j] = W[j][i];
	int cyc = 0;
	L(i, 1, cnt) {
		int ok = 1;
		L(j, 1, cnt - i) ok &= F[j] == F[j + i];
		if(ok) {
			cyc = i;
			break;
		}
	}
	assert(cyc >= 500); 
	
	L(p, 1, cyc) {
		ll P = (cn - p + cyc) / cyc;
		len[i] += P * F[p];
	}
	
	}
	ll ans = 0;
	L(i, 1, m) ans += min(len[i], cm);
	cout << ans << '\n';
	return 0;
}