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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
public class B314 
{
    static class Scanner
    {
        BufferedReader br;
        StringTokenizer tk=new StringTokenizer("");
        public Scanner(InputStream is) 
        {
            br=new BufferedReader(new InputStreamReader(is));
        }
        public int nextInt() throws IOException
        {
            if(tk.hasMoreTokens())
                return Integer.parseInt(tk.nextToken());
            tk=new StringTokenizer(br.readLine());
            return nextInt();
        }
        public long nextLong() throws IOException
        {
            if(tk.hasMoreTokens())
                return Long.parseLong(tk.nextToken());
            tk=new StringTokenizer(br.readLine());
            return nextLong();
        }
        public String next() throws IOException
        {
            if(tk.hasMoreTokens())
                return (tk.nextToken());
            tk=new StringTokenizer(br.readLine());
            return next();
        }
        public String nextLine() throws IOException
        {
            tk=new StringTokenizer("");
            return br.readLine();
        }
        public double nextDouble() throws IOException
        {
            if(tk.hasMoreTokens())
                return Double.parseDouble(tk.nextToken());
            tk=new StringTokenizer(br.readLine());
            return nextDouble();
        }
        public char nextChar() throws IOException
        {
            if(tk.hasMoreTokens())
                return (tk.nextToken().charAt(0));
            tk=new StringTokenizer(br.readLine());
            return nextChar();
        }
        public int[] nextIntArray(int n) throws IOException
        {
            int a[]=new int[n];
            for(int i=0;i<n;i++)
                a[i]=nextInt();
            return a;
        }
        public long[] nextLongArray(int n) throws IOException
        {
            long a[]=new long[n];
            for(int i=0;i<n;i++)
                a[i]=nextLong();
            return a;
        }
        public int[] nextIntArrayOneBased(int n) throws IOException
        {
            int a[]=new int[n+1];
            for(int i=1;i<=n;i++)
                a[i]=nextInt();
            return a;
        }
        public long[] nextLongArrayOneBased(int n) throws IOException
        {
            long a[]=new long[n+1];
            for(int i=1;i<=n;i++)
                a[i]=nextLong();
            return a;
        }
    
    
    }
    
    public static void main(String args[]) throws IOException
    {
        Scanner in=new Scanner(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int b=in.nextInt();
        int d=in.nextInt();
        String s1=in.next();
        String s2=in.next();
        boolean f[]=new boolean[26];
        for(int i=0;i<s1.length();i++)
            f[s1.charAt(i)-'a']=true;
        for(int i=0;i<s2.length();i++)
        {
            if(!f[s2.charAt(i)-'a'])
            {
                System.out.println(0);
                return;
            }
        }
        Arrays.fill(f,false);
        for(int i=0;i<s2.length();i++)
            f[s2.charAt(i)-'a']=true;
        String sx="";
        for(int i=0;i<s1.length();i++)
        {
            char c=s1.charAt(i);
            if(f[c-'a'])
                sx+=c;
                    
        }
        char a[]=sx.toCharArray();
        char c[]=s2.toCharArray();
        
        int n1=a.length,n2=c.length;
        long x1=b*a.length;
        int y[]=new int[n1];
        int nx[]=new int[n1];
        for(int i=0;i<n1;i++)
        {
            //count no. of chars required when starting from i in a
            int i1=i,i2=0,cnt=0;
            while(true)
            {
                cnt++;
                if(a[i1]==c[i2])
                {
                    i1++;
                    i2++;
                }
                else
                    i1++;
                if(i1==n1)
                    i1=0;
                if(i2==n2)
                    break;
                
            }
            y[i]=cnt;
            nx[i]=i1;
        }
        //count no of matches
        int st=0;
        long tot=0;
        int cnt=0;
        boolean flag=false;
        while(tot<x1)
        {
            tot+=y[st];
            cnt++;
            st=nx[st];
            if(st==0)
            {
                if(tot<x1)
                {
                    long q=x1/tot;
                    tot*=q;
                    cnt*=q;
                }
            }
        }
        
        if(tot>x1)
            cnt--;
        out.println(cnt/d);
        out.close();
    }

}
