Let's introduce the designation <image>, where x is a string, n is a positive integer and operation " + " is the string concatenation operation. For example, [abc, 2] = abcabc.

We'll say that string s can be obtained from string t, if we can remove some characters from string t and obtain string s. For example, strings ab and aсba can be obtained from string xacbac, and strings bx and aaa cannot be obtained from it.

Sereja has two strings, w = [a, b] and q = [c, d]. He wants to find such maximum integer p (p > 0), that [q, p] can be obtained from string w.

Input

The first line contains two integers b, d (1 ≤ b, d ≤ 107). The second line contains string a. The third line contains string c. The given strings are not empty and consist of lowercase English letters. Their lengths do not exceed 100.

Output

In a single line print an integer — the largest number p. If the required value of p doesn't exist, print 0.

Examples

Input

10 3
abab
bab


Output

3
import java.io.*;

import static java.lang.Math.*;
import java.util.*;
import static java.util.Arrays.fill;
import static java.util.Arrays.sort;

public class Main {
	public static void main(String[] args) {
		if(new File("input.txt").exists())
			try {
				System.setIn(new FileInputStream("input.txt"));
			} catch (FileNotFoundException e1) {
				e1.printStackTrace();
			}
		new Thread(null, new Runnable() {
			public void run() {
				try {
					new Main().run();
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
		}, "kek", 1 << 23).start();
	}

	BufferedReader in;
	PrintWriter out;
	StringTokenizer st = new StringTokenizer("");
	
	
	void run() throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		Locale.setDefault(Locale.US);
		solve();
		in.close();
		out.close();
	}
	
	

	void solve() throws IOException{

		int a = nextInt();
		int b = nextInt();
		
		String sa = nextToken();
		String sb = nextToken();
		
		for(int j = 0; j < sb.length(); j++)
			if(!sa.contains(sb.charAt(j) + "")){
				out.println(0);
				return;
			}

		int[][] stepsA = new int[sa.length()][sb.length()];
		int[][] stepsB = new int[sa.length()][sb.length()];

		for(int row[] : stepsA)
			fill(row, -1);
		for(int row[] : stepsB)
			fill(row, -1);
		
		int p1 = 0;
		int p2 = 0;
		int curStepA = 0;
		int curStepB = 0;
		stepsA[p1][p2] = curStepA;
		stepsB[p1][p2] = curStepB;
		
		int lenA = sa.length();
		int lenB = sb.length();
		
		int startA = -1, startB = -1;
		int loopA = -1;
		int loopB = -1;
		
		
		while(true){
			if(sa.charAt(p1 % lenA) == sb.charAt(p2 % lenB)){
				p1++;
				p2++;
				curStepB++;
			} else
				p1++;
			curStepA++;
			if(stepsA[p1 % lenA][p2 % lenB] != -1){
				startA = p1;
				startB = p2;
				loopA = curStepA - stepsA[p1 % lenA][p2%lenB];
				loopB = curStepB - stepsB[p1 % lenA][p2%lenB];
				break;
			}
			stepsA[p1 % lenA][p2%lenB] = curStepA;
			stepsB[p1 % lenA][p2%lenB] = curStepB;
		}
		
		
		int A = 0, B = 0;
		long szA = sa.length() * a;
		
		boolean ok = false;
		if(startA < szA){
			A = startA;
			B = startB;
			ok = true;
		}

		long k = (szA - 1 - A) / loopA;
//		System.err.println(loopA + " | " + loopB + " ||| " + A + " " + B);
		B += loopB * k;
		A += loopA * k;
//		System.err.println(szA);
		while(A < szA){
			if(sa.charAt(A % lenA) == sb.charAt(B % lenB)){
				A++;
				B++;
			} else
				A++;
		}
//		System.err.println("?? " + A + " | " + B);
		out.println(B / (lenB * b));
		
	}
	
	
	
	
	String nextToken() throws IOException{
		while(!st.hasMoreTokens())
			st = new StringTokenizer(in.readLine());
		return st.nextToken();
	}
	long nextLong() throws IOException{
		return Long.parseLong(nextToken());
	}
	int nextInt() throws IOException{
		return Integer.parseInt(nextToken());
	}
	double nextDouble() throws IOException{
		return Double.parseDouble(nextToken());
	}
}
