#include <bits/stdc++.h>
using namespace std;
long long nextLetter[101][101][61];
long long needed[101][101][61];
long long b, d;
string a, c;
int n, m;
int can = 1;
long long GetTimes(long long bTimes) {
  int currentLetter = 0;
  long long times = 0;
  for (long long k = (61 - 1); k >= 0; k--) {
    if (bTimes & (1LL << k)) {
      times += needed[currentLetter][0][k];
      currentLetter = nextLetter[currentLetter][0][k];
    }
  }
  if (currentLetter > 0) times++;
  return times;
}
int main() {
  cin >> b >> d >> a >> c;
  n = a.size();
  m = c.size();
  for (int(j) = (0); (j) < (m); (j)++) {
    int currentlyCan = 0;
    for (int(i) = (0); (i) < (n); (i)++) {
      if (a[i] == c[j]) currentlyCan = 1;
    }
    can = can && currentlyCan;
  }
  if (!can) {
    cout << 0 << "\n";
    return 0;
  }
  for (int j = m - 1; j >= 0; j--) {
    for (int(i) = (0); (i) < (n); (i)++) {
      int current = i;
      int wrapped = 0;
      while (a[current] != c[j]) {
        current = (current + 1) % n;
        if (current == 0) wrapped = 1;
      }
      current = (current + 1) % n;
      if (current == 0) wrapped = 1;
      if (j == (m - 1)) {
        nextLetter[i][j][0] = current;
        needed[i][j][0] = wrapped;
      } else {
        nextLetter[i][j][0] = nextLetter[current][j + 1][0];
        needed[i][j][0] = wrapped + needed[current][j + 1][0];
      }
    }
  }
  for (int k = 1; k < 61; k++) {
    for (int(i) = (0); (i) < (n); (i)++) {
      int firstLetter = nextLetter[i][0][k - 1];
      int firstNeeded = needed[i][0][k - 1];
      nextLetter[i][0][k] = nextLetter[firstLetter][0][k - 1];
      needed[i][0][k] = firstNeeded + needed[firstLetter][0][k - 1];
    }
  }
  if (GetTimes(d) > b) {
    cout << 0 << "\n";
    return 0;
  }
  long long lo = 1, hi = 1e9 + 1;
  while (lo < hi) {
    long long mid = (lo + hi + 1) / 2;
    long long timesNeeded = GetTimes(d * mid);
    int can = timesNeeded <= b;
    if (can)
      lo = mid;
    else
      hi = mid - 1;
  }
  cout << lo << "\n";
}
