#include <bits/stdc++.h>
using namespace std;
using ll = __int128;
using ull = unsigned ll;
// msvc does not overload numeric_limits for int128
constexpr ll linf = numeric_limits<long long>::max() * (ll)numeric_limits<long long>::max();
template<class T>
ll ssize(const T &t)
{
return ll(t.size());
}
vector<ll> solve_one_infty(string_view a, string_view b)
{
vector<ll> ans(b.size());
iota(ans.begin(), ans.end(), 0);
auto nxt = [&b](auto t)
{
return t + 1 == b.size() ? 0 : t + 1;
};
for (auto it: a)
{
auto st = b.find(it);
auto pos = st;
auto prev = ans[st];
do
{
pos = nxt(pos);
if (pos == 0)
prev -= ssize(b);
if (b[pos] == it || prev > ans[pos])
swap(prev, ans[pos]);
} while (pos != st);
}
return ans;
}
template<class T>
T &remin(T &x, const T &y)
{
return x = min(x, y);
}
vector<vector<int>> knuth_tropical_multiplication(const vector<vector<int>> &a, const vector<vector<int>> &b)
{
vector<vector<int>> c(a.size(), vector<int>(b[0].size(), numeric_limits<int>::max()));
vector<vector<int>> opt(a.size(), vector<int>(b[0].size()));
for (int l = 0; l < int(a.size()); l++)
for (int r = int(b[0].size()) - 1; r >= 0; r--)
{
const int left_ptr = (l == 0 ? 0 : opt[l - 1][r]);
const int right_ptr = (r == int(b[0].size()) - 1 ? int(b.size()) - 1 : opt[l][r + 1]);
int res_ptr = left_ptr, res = numeric_limits<int>::max();
for (int ptr = left_ptr; ptr <= right_ptr; ptr++)
{
const int cur = a[l][ptr] + b[ptr][r];
if (res > cur)
{
res = cur;
res_ptr = ptr;
}
}
c[l][r] = res;
opt[l][r] = res_ptr;
}
return c;
}
vector<int> uncore(const vector<vector<int>> &t)
{
vector<int> perm(t.size() - 1, -1);
for (int i = 0; i + 1 < ssize(t); i++)
for (int j = 1; j < ssize(t[i]); j++)
if (t[i][j] == t[i + 1][j] + 1 && t[i + 1][j] == t[i][j - 1] && t[i + 1][j - 1] == t[i][j - 1])
perm[i] = j - 1;
assert(count(perm.begin(), perm.end(), -1) == 0);
return perm;
}
vector<vector<int>> core(const vector<int> &a)
{
vector<vector<int>> pm(a.size() + 1, vector<int>(a.size() + 1));
for (int i = ssize(pm) - 2; i >= 0; i--)
{
pm[i] = pm[i + 1];
for (int j = a[i] + 1; j < ssize(pm[i]); j++)
pm[i][j]++;
}
assert(a == uncore(pm));
return pm;
}
vector<int> permutation_multiplication(const vector<int> &a, const vector<int> &b)
{
return uncore(knuth_tropical_multiplication(core(a), core(b)));
}
ll py_divison(ll a, ll b)
{
assert(b > 0);
auto ans = a / b;
if (a % b < 0)
ans -= 1;
return ans;
}
ll period(const vector<ll> &b, ll it)
{
return py_divison(ll(b.size() - 1) - it, ssize(b));
}
vector<int> inverse_permutation(const vector<int> &arr)
{
vector<int> ans(arr.size());
for (int i = 0; i < ssize(arr); i++)
ans[arr[i]] = i;
return ans;
}
vector<ll> inverse_permutation(const vector<ll> &arr)
{
vector<ll> ans(arr.size());
for (int i = 0; i < ssize(arr); i++)
{
auto per = period(arr, arr[i]);
auto sh = per * ssize(arr);
ans[arr[i] + sh] = i + sh;
}
return ans;
}
vector<ll> repeat(const vector<ll> &arr, int k)
{
vector<ll> ans;
ans.reserve(arr.size() * k);
for (int i = 0; i < k; i++)
for (auto it: arr)
ans.push_back(it + i * ssize(arr));
return ans;
}
vector<ll> inf_permutation_multiplication(const vector<ll> &up, const vector<ll> &down)
{
auto a = repeat(up, 3);
auto b = repeat(down, 3);
assert(a.size() == b.size());
auto ib = inverse_permutation(b);
auto starts = a;
auto ends = ib;
sort(starts.begin(), starts.end());
sort(ends.begin(), ends.end());
vector<int> pa, pib;
pa.reserve(a.size());
pib.reserve(a.size());
auto shrink = [](const vector<ll> &arr, ll x)
{
auto it = lower_bound(arr.begin(), arr.end(), x);
assert(it != arr.end() && *it == x);
return int(it - arr.begin());
};
for (auto it: a)
pa.push_back(shrink(starts, it));
for (auto it: ib)
pib.push_back(shrink(ends, it));
auto pb = inverse_permutation(pib);
auto pans = permutation_multiplication(pb, pa);
auto ipans = inverse_permutation(pans);
vector<ll> ans(up.size(), linf);
auto ind_per = [&up](ll x) -> pair<ll, ll>
{
auto per = period(up, x);
ll sh = per * ssize(up);
return {x + sh, per};
};
auto add = [&](ll start, ll end)
{
auto [qa, pera] = ind_per(start);
auto [qb, perb] = ind_per(end);
ans.at(qb) = qa - (pera - perb) * ssize(up);
};
for (auto i = ssize(up); i < 2 * ssize(up); i++)
{
auto q = pa[i];
auto w = ipans[q];
add(starts.at(q), ends.at(w));
}
assert(count(ans.begin(), ans.end(), linf) == 0);
return ans;
}
template<class T, class F>
T bin_pow(const T &a, ull y, const F &mult)
{
assert(y > 0);
if (y == 1)
return a;
if (y % 2 != 0)
return mult(bin_pow(a, y - 1, mult), a);
auto q = bin_pow(a, y / 2, mult);
return mult(q, q);
}
vector<ll> solve_infty_infty(string_view a, string_view b, ull rep)
{
auto perm = solve_one_infty(a, b);
return bin_pow(perm, rep, inf_permutation_multiplication);
}
void test(string_view a, string_view b, int wh)
{
auto ans = solve_one_infty(a, b);
auto sa = solve_one_infty(a.substr(0, wh), b);
auto sb = solve_one_infty(a.substr(wh), b);
auto sc = inf_permutation_multiplication(sa, sb);
assert(sc == ans);
}
void solve(istream &cin = std::cin, ostream &cout = std::cout)
{
long long l, k;
cin >> l >> k;
string a, b;
cin >> a >> b;
if (k < l)
{
swap(k, l);
swap(a, b);
}
auto remove_unique = [](string &a, string_view b)
{
a.resize(remove_if(a.begin(), a.end(), [&](char ch)
{
return b.find(ch) == string_view::npos;
}) - a.begin());
};
remove_unique(a, b);
remove_unique(b, a);
if (a.empty() || b.empty())
{
cout << 0 << endl;
return;
}
auto perm = solve_infty_infty(a, b, l);
ll ans = 0;
for (auto it: perm)
ans += min((ll) k, period(perm, it));
cout << (long long) ans << endl;
}
ll naive_lcs(string_view a, string_view b)
{
vector<ll> dp(b.size() + 1);
vector<ll> tmp(dp.size());
for (auto it: a)
{
for (size_t i = 1; i < tmp.size(); i++)
if (b[i - 1] == it)
tmp[i] = dp[i - 1] + 1;
else
tmp[i] = max(tmp[i - 1], dp[i]);
swap(dp, tmp);
}
return dp.back();
}
void stress(istream &cin = std::cin, ostream &cout = std::cout)
{
long long l, k;
cin >> l >> k;
string a, b;
cin >> a >> b;
string la, kb;
for (int i = 0; i < l; i++)
la += a;
for (int i = 0; i < k; i++)
kb += b;
cout << (long long) naive_lcs(la, kb) << endl;
}
void gen(ostream &cout = std::cout)
{
static mt19937 mt(736);
uniform_int_distribution<long long> uid(1, 1e3), sz(1, 100);
cout << uid(mt) << " " << uid(mt) << endl;
auto sa = sz(mt);
auto sb = sz(mt);
uniform_int_distribution<char> ch('a', 'd');
for (int i = 0; i < sa; i++)
cout << ch(mt);
cout << endl;
for (int i = 0; i < sb; i++)
cout << ch(mt);
cout << endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed;
#ifdef LOCAL
auto st = chrono::steady_clock::now();
ifstream fin("../input.txt");
do
{
solve(fin);
cout << "===" << endl;
string str;
while (getline(fin, str) && str != string(max(1, (int) str.size()), '='));
} while (fin);
#ifdef STRESS
for (int cnt = 1;; cnt++)
{
stringstream ss, in1, out1, in2, out2;
gen(ss);
in1 << ss.str();
in2 << ss.str();
solve(in1, out1);
stress(in2, out2);
if (out1.str() != out2.str())
{
cout << "fail: " << cnt << endl;
cout << ss.str();
cout << "solve:" << endl;
cout << out1.str();
cout << "stress:" << endl;
cout << out2.str();
break;
}
else if (cnt % 1 == 0)
cout << "ok: " << cnt << endl;
}
#endif
cout << setprecision((int) floor(log10(chrono::steady_clock::duration::period::den)));
cout << "clock: " << chrono::duration<double>(chrono::steady_clock::now() - st).count() << endl;
#else
solve();
#endif
return 0;
}