#include <bits/stdc++.h>

using namespace std;


using ll = __int128_t;

#define int ll
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, n) for(int i = 0; i < n; i += 1)
#define len(a) (int(a.size()))
// #define assert(a) if(!(a)) {while(true){}}


const ll inf = 1e18;
mt19937 rnd(234);


ostream& operator<<(ostream& out, __int128_t x) {
    return out << (long long)x;
}


istream& operator>>(istream& in, __int128_t& x) {
    long long a;
    in >> a;
    x = a;
    return in;
}



ll solve(ll n, ll m, string a, string b, bool stupid = false) {
    string na, nb;
    for (auto x : a) {
        if (find(all(b), x) != b.end()) {
            na.push_back(x);
        }
    }
    for (auto x : b) {
        if (find(all(a), x) != a.end()) {
            nb.push_back(x);
        }
    }
    a = na;
    b = nb;
    if (a.empty() or b.empty()) {
        return 0;
    }
    if (stupid) {
        na = "";
        rep(i, n) na += a;
        n = 1;
        a = na;
    }

    int s = len(a);
    int t = len(b);
    vector<ll> p(t);
    rep(i, t) p[i] = i;
    for (int i = 0; i < s; i += 1) {
        int first_same = -1;
        rep(j, t) if (a[i] == b[j]) { first_same = j; break; }
        assert(first_same != -1);
        vector<ll> np(t);
        for (int l = first_same; ; ) {
            int r = (l + 1) % t;
            while (a[i] != b[r]) {
                r = (r + 1) % t;
            }
            ll cur = p[l];
            if (l == t - 1) {
                cur -= t;
            }
            for (int j = (l + 1) % t; j != r; j = (j + 1) % t) {
                ll val = p[j];
                assert(val != cur);
                if (val < cur) {
                    np[j] = cur;
                    cur = val;
                } else {
                    np[j] = val;
                }
                if (j == t - 1) {
                    cur -= t;
                }
            }
            np[r] = cur;
            if (r == first_same) {
                break;
            }
            l = r;
        }
        p = np;
    }
    auto check_perm = [&](vector<ll> x) {
        for (auto& v : x) {
            v = ((v % t) + t) % t;
        }
        sort(all(x));
        rep(i, t) if (x[i] != i) return false;
        return true;
        };
    assert(check_perm(p));
    auto merge = [&](const vector<ll>& p, const vector<ll>& q) {
        vector<ll> invq(t, t);
        rep(i, t) {
            ll val = q[i];
            ll r = ((val % t) + t) % t;
            ll d = (val - r) / t;
            assert(d <= 0);
            invq[r] = (-d) * t + i;
        }
        assert(check_perm(invq));
        vector<ll> biba, boba;
        vector<ll> base;
        rep(i, t) {
            biba.push_back(p[i]);
            biba.push_back(p[i] + t);
            biba.push_back(p[i] + 2 * t);

            base.push_back(p[i] + t);

            boba.push_back(invq[i]);
            boba.push_back(invq[i] + t);
            boba.push_back(invq[i] + 2 * t);
        }
        sort(all(biba));
        sort(all(boba));
        sort(all(base));
        biba.resize(unique(all(biba)) - biba.begin());
        boba.resize(unique(all(boba)) - boba.begin());
        base.resize(unique(all(base)) - base.begin());
        assert(len(biba) == 3 * t);
        assert(len(boba) == 3 * t);
        assert(len(base) == t);
        vector<ll> a(3 * t), b(3 * t);
        rep(i, t) {
            a[i] = lower_bound(all(biba), p[i]) - biba.begin();
            a[i + t] = lower_bound(all(biba), p[i] + t) - biba.begin();
            a[i + 2 * t] = lower_bound(all(biba), p[i] + 2 * t) - biba.begin();

            b[lower_bound(all(boba), invq[i]) - boba.begin()] = i;
            b[lower_bound(all(boba), invq[i] + t) - boba.begin()] = i + t;
            b[lower_bound(all(boba), invq[i] + 2 * t) - boba.begin()] = i + 2 * t;
        }
        vector<pair<int, int>> swaps;
        while (true) {
            bool flag = false;
            for (int i = 0; i + 1 < 3 * t; i += 1) {
                if (b[i] > b[i + 1]) {
                    swaps.push_back(make_pair(i, i + 1));
                    swap(b[i], b[i + 1]);
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
        reverse(all(swaps));
        for (auto [i, j] : swaps) {
            if (a[i] < a[j]) {
                swap(a[i], a[j]);
            }
        }
        vector<ll> result(t, t);
        rep(i, 3 * t) {
            int j = a[i];
            ll x = biba[j];
            if (binary_search(all(base), x)) {
                ll y = boba[i];
                ll ry = (y % t + t) % t;
                result[ry] = (x - (y - ry));
            }
        }
        assert(check_perm(result));
        return result;
        };
    function<vector<ll>(const vector<ll>&, int)> bin_pow;
    bin_pow = [&](const vector<ll>& p, int n) {
        if (n == 0) {
            vector<ll> res(t); rep(i, t) res[i] = i; return res;
        }
        auto a = bin_pow(p, n / 2);
        a = merge(a, a);
        if (n & 1) {
            a = merge(a, p);
        }
        return a;
        };
    auto q = bin_pow(p, n);
    ll result = 0;
    rep(i, t) {
        if (q[i] >= 0) {
            continue;
        }
        ll f = (-q[i] + t - 1) / t;
        result += min(f, m);
    }
    return result;
}


ll stupid_solve(ll n, ll m, string a, string b) {
    string na, nb;
    rep(i, n) na += a;
    rep(i, m) nb += b;
    a = na;
    b = nb;
    ll s = len(a); ll t = len(b);
    vector<vector<ll>> dp(s + 1, vector<ll>(t + 1, 0));
    rep(i, s) rep(j, t) dp[i + 1][j + 1] = max({ dp[i][j + 1], dp[i + 1][j], dp[i][j] + ll(a[i] == b[j]) });
    return dp[s][t];
}


void stress() {
    int c = 0;
    while (true) {
        cout << ++c << "\n";
        ll n = rnd() % 100 + 1;
        ll m = rnd() % 100 + 1;
        ll s = rnd() % 100 + 1;
        ll t = rnd() % 100 + 1;
        string a, b;
        a.resize(s); b.resize(t);
        rep(i, s) a[i] = 'a' + rnd() % 10;
        rep(i, t) b[i] = 'a' + rnd() % 10;
        ll right_rs = stupid_solve(n, m, a, b);
        ll my_rs = solve(n, m, a, b);
        if (right_rs != my_rs) {
            cout << "\n\n";
            cout << n << " " << m << "\n";
            cout << a << "\n";
            cout << b << "\n";
            cout << "\n\n";
            cout << my_rs << " " << right_rs << "\n";
            break;
        }
    }
}

int32_t main() {
    // stress();
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    ll n, m;
    cin >> n >> m;
    string a, b;
    cin >> a >> b;
    ll result = solve(n, m, a, b);
    cout << result << "\n";
    return 0;
}