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


from itertools import repeat,chain
from fractions import gcd

def eternal(c,d, n = None):


    while True:

        yield chain.from_iterable(repeat(c,d))



        


def cyclic_array(arr):

    n = len(arr)
    def cyclar(i):

        return arr[i % n]

    return cyclar
def find_repeat(enum,q_r_gen, a_n):

    ac_count =0
    a_count = 0
    remainders ={}
    tempq=''
    tempa = ''
    for q,q_r in enumerate(q_r_gen):

        tempq=''
        for c_c in q_r:
            tempq= tempq +c_c
            for a_count,a_c in enum:
                if a_c == c_c:
                    tempa = tempa +a_c
                    ac_count+=1
                    break
            #print len(tempa),len(tempq)
        if (a_count % a_n) in remainders:

            #print tempq[:20],tempa[:20]
            break
        else:

            remainders[(a_count % a_n)]=(a_count,q)

    repeat_length = a_count - remainders[a_count % a_n][0]
    q_count = q-remainders[a_count % a_n][1]

    return remainders[a_count % a_n][0],repeat_length,q_count
    


    
def main(a,b,c,d):
  

    
    #print a, c


    a_r = chain.from_iterable(repeat(a,b))

    #print "".join(chain.from_iterable(repeat(a,b)))


    enum =enumerate(a_r)

    q_r_gen = eternal(c,d)

    i = 0
    flag = True


    if len(a) > len(c)*d:
        multiplier =1
        start,repeat_length,q_count = find_repeat(enum,q_r_gen, len(a))

    else:
        multiplier =((len(c)*d)//len(a))+1
        #print "Multi",multiplier
        enum2 = enumerate(chain.from_iterable(repeat(a*multiplier,b//multiplier)))
        start,repeat_length,q_count =find_repeat(enum2,q_r_gen, multiplier*len(a))
        
    if repeat_length >0:
        advance_n = (((len(a)*multiplier)*(b//multiplier))//repeat_length)-1
        advance = repeat_length * advance_n

        sofar = q_count * advance_n
    else:
        advance_n =0
        advance = 0
        sofar = 0

    #print advance_n,advance, repeat_length, len(a)*b, sofar , len(c)*d
        
    ca = cyclic_array(a)

    ra = iter(range(advance,len(a)*b))

    ac_count =0
    for q_r in q_r_gen:
        for i,c_c in enumerate(q_r):

            flag = False
            for a_count in ra:
                #print a_count

                if ca(a_count) == c_c:
                    ac_count+=1
                    flag = True
                    break
                
        if not flag:
            break

    
    print sofar + (ac_count // (len(c)*d))


    
if __name__ == "__main__":
    b,d = [int(s) for s in (raw_input()).split()]

    a = raw_input()

    c = raw_input()

    aset = set(a)
    cset = set(c)

    if cset.difference(aset):
        print 0

    elif a == c:

        print b // d
        
    else:
        
        main(a,b,c,d)
    