#include <bits/stdc++.h>

using namespace std;

#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;
}
using ll = long long;

#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);



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);
            base.push_back(p[i] + t);
            biba.push_back(p[i] + 2 * 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() % 10 + 1;
        ll t = rnd() % 10 + 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;
}

answer.code:273: warning: "assert" redefined
  273 | #define assert(a) if(!(a)) {while(true){}}
      | 
In file included from /usr/include/c++/13/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:106,
                 from answer.code:5:
/usr/include/assert.h:92: note: this is the location of the previous definition
   92 | #  define assert(expr)                                                  \
      | 
answer.code:265:7: error: conflicting declaration ‘using ll = long long int’
  265 | using ll = long long;
      |       ^~
answer.code:10:7: note: previous declaration as ‘using ll = __int128’
   10 | using ll = __int128_t;
      |       ^~
answer.code:276:10: error: redefinition of ‘const ll inf’
  276 | const ll inf = 1e18;
      |          ^~~
answer.code:21:10: note: ‘const ll inf’ previously defined here
   21 | const ll inf = 1e18;
      |          ^~~
answer.code:277:9: error: redefinition of ‘std::mt19937 rnd’
  277 | mt19937 rnd(234);
      |         ^~~
answer.code:22:9: note: ‘std::mt19937 rnd’ previously declared here
   22 | mt19937 rnd(234);
      |         ^~~
answer.code:281:4: error: redefinition of ‘ll solve(ll, ll, std::string, std::string, bool)’
  281 | ll solve(ll n, ll m, string a, string b, bool stupid = false) {
      |    ^~~~~
answer.code:39:4: note: ‘ll solve(ll, ll, std::string, std::string, bool)’ previously defined here
   39 | ll solve(ll n, ll m, string a, string b, bool stupid = false) {
      |    ^~~~~
answer.code:452:4: error: redefinition of ‘ll stupid_solve(ll, ll, std::string, std::string)’
  452 | ll stupid_solve(ll n, ll m, string a, string b) {
      |    ^~~~~~~~~~~~
answer.code:211:4: note: ‘ll stupid_solve(ll, ll, std::string, std::string)’ previously defined here
  211 | ll stupid_solve(ll n, ll m, string a, string b) {
      |    ^~~~~~~~~~~~
answer.code:465:6: error: redefinition of ‘void stress()’
  465 | void stress() {
      |      ^~~~~~
answer.code:224:6: note: ‘void stress()’ previously defined here
  224 | void stress() {
      |      ^~~~~~
answer.code:491:9: error: redefinition of ‘int32_t main()’
  491 | int32_t main() {
      |         ^~~~
answer.code:250:9: note: ‘int32_t main()’ previously defined here
  250 | int32_t main() {
      |         ^~~~
In file included from /usr/include/c++/13/functional:59,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53,
                 from answer.code:1:
/usr/include/c++/13/bits/std_function.h:124:27: error: mangling of ‘const bool std::_Function_base::_Base_manager<solve(ll, ll, std::string, std::string, bool)::<lambda(const std::vector<__int128>&, ll)> >::__stored_locally’ as ‘_ZNSt14_Function_base13_Base_managerIZ5solvennNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEES6_bEUlRKSt6vectorInSaInEEnE_E16__stored_locallyE’ conflicts with a previous mangle
  124 |         static const bool __stored_locally =
      |                           ^~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/std_function.h:124:27: note: previous mangling ‘const bool std::_Function_base::_Base_manager<solve(ll, ll, std::string, std::string, bool)::<lambda(const std::vector<__int128>&, ll)> >::__stored_locally’
/usr/include/c++/13/bits/std_function.h:124:27: note: a later ‘-fabi-version=’ (or =0) avoids this error with a change in mangling
/usr/include/c++/13/bits/std_function.h:158:11: error: mangling of ‘static void std::_Function_base::_Base_manager<_Functor>::_M_create(std::_Any_data&, _Fn&&, std::false_type) [with _Fn = const solve(ll, ll, std::string, std::string, bool)::<lambda(const std::vector<__int128>&, ll)>&; _Functor = solve(ll, ll, std::string, std::string, bool)::<lambda(const std::vector<__int128>&, ll)>]’ as ‘_ZNSt14_Function_base13_Base_managerIZ5solvennNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEES6_bEUlRKSt6vectorInSaInEEnE_E9_M_createIRKSC_EEvRSt9_Any_dataOT_St17integral_constantIbLb0EE’ conflicts with a previous mangle
  158 |           _M_create(_Any_data& __dest, _Fn&& __f, false_type)
      |           ^~~~~~~~~
/usr/include/c++/13/bits/std_function.h:158:11: note: previous mangling ‘static void std::_Function_base::_Base_manager<_Functor>::_M_create(std::_Any_data&, _Fn&&, std::false_type) [with _Fn = const solve(ll, ll, std::string, std::string, bool)::<lambda(const std::vector<__int128>&, ll)>&; _Functor = solve(ll, ll, std::string, std::string, bool)::<lambda(const std::vector<__int128>&, ll)>]’
/usr/include/c++/13/bits/std_function.h:158:11: note: a later ‘-fabi-version=’ (or =0) avoids this error with a change in mangling
In file included from /usr/include/c++/13/bits/stl_pair.h:61,
                 from /usr/include/c++/13/bits/stl_algobase.h:64,
                 from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51:
/usr/include/c++/13/bits/move.h:70:5: error: mangling of ‘constexpr _Tp&& std::forward(typename remove_reference<_Functor>::type&) [with _Tp = const solve(ll, ll...