#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(0);
  int k1, k2;
  cin >> k1 >> k2;
  string s1, s2;
  cin >> s1 >> s2;
  int n1 = (int)(s1).size(), n2 = (int)(s2).size();
  for (int i = (0); i <= ((int)(s2).size() - 1); ++i) {
    bool is_there = 0;
    for (int j = (0); j <= ((int)(s1).size() - 1); ++j)
      if (s1[j] == s2[i]) is_there = 1;
    if (!is_there) {
      cout << 0;
      return 0;
    }
  }
  vector<vector<vector<int> > > L(32), T(32);
  for (int i = (0); i <= ((int)(L).size() - 1); ++i) {
    L[i].resize(n1);
    T[i].resize(n1);
    for (int j = (0); j <= ((int)(L[i]).size() - 1); ++j) {
      L[i][j].resize(n2, 0);
      T[i][j].resize(n2, 0);
    }
  }
  for (int i = (0); i <= ((int)(s1).size() - 1); ++i)
    for (int j = (0); j <= ((int)(s2).size() - 1); ++j) {
      int it = i;
      while (s1[it] != s2[j]) it = (it + 1) % n1;
      T[0][i][j] = (it + 1) % n1;
      L[0][i][j] = (it < i);
    }
  for (int b = (1); b <= (32 - 1); ++b)
    for (int i = (0); i <= ((int)(s1).size() - 1); ++i)
      for (int j = (0); j <= ((int)(s2).size() - 1); ++j) {
        L[b][i][j] = L[b - 1][i][j];
        int it_i = T[b - 1][i][j], it_j = (j + (1 << (b - 1))) % n2;
        if (it_i == 0) L[b][i][j]++;
        L[b][i][j] += L[b - 1][it_i][it_j];
        T[b][i][j] = T[b - 1][it_i][it_j];
        L[b][i][j] =
            (((L[b][i][j]) < (1000000001)) ? (L[b][i][j]) : (1000000001));
      }
  int l = 0, r = 1000000001;
  while (r - l > 1) {
    int mid = (l + r) / 2, i = 0, j = 0, ans = 0;
    long long int k = (long long int)mid * n2 * k2;
    if (k < 1000000001) {
      for (int b = (0); b <= (32 - 1); ++b)
        if (k)
          if ((k & (1 << b))) {
            k ^= (1 << b);
            ans += L[b][i][j];
            ans = (((ans) < (1000000001)) ? (ans) : (1000000001));
            if (i == 0) ans++;
            i = T[b][i][j];
            j = (j + (1 << b)) % n2;
          }
    } else
      ans = 1000000001;
    if (ans > k1)
      r = mid;
    else
      l = mid;
  }
  cout << l;
  return 0;
}
