Benny is given two strings S and T. The length of the string S is N and the length of the string T is M respectively. 

Also, imagine that alphabets are cyclic in nature: a-b-c-…-x-y-z-a-b.. and so on. The distance between two letters is the minimal distance between them in the alphabet cycle.  For example, distance between ‘a’ and ‘c’ is 2, when distance between ‘b’ and ‘z’ is 2.

Let’s call the process transformation when one letter turns to another one. The cost of the transformation is the distance between these letters.

She may perform some transformations in string T, but the total cost of these transformations should not exceed K.

Now, she wants to make a string T’ from the given string T such that S appears the most times in T’ as a substring.

For example, abc is a substring of ababc but bac is not a substring of ababc.

Output the maximal numbers of occurrences of string S in T’ after making transformations with total cost not more that K.

Input format

The first line contains three space separated integers N, M and K.

The next two lines contain strings S and and T respectively.

Output format

Print in a single line an answer to the problem.

Constraints
1 ≤ N, M ≤ 200
0 ≤ K ≤ 500

Note
Strings contain only lowercase English letters.

SAMPLE INPUT
3 5 3
aba
zbzbz

SAMPLE OUTPUT
2

Explanation

In the given sample case, she can make ababa from zbzbz. The cost of transformation is not more that K. The number of occurrences of aba in ababa are 2. Hence, the answer is 2.
#!/usr/bin/env python
#-*- coding:utf-8 -*-

import sys, math, random, operator
from string import ascii_lowercase
from string import ascii_uppercase
from fractions import Fraction, gcd
from decimal import Decimal, getcontext
from itertools import product, permutations, combinations
from Queue import Queue, PriorityQueue
from collections import deque, defaultdict, Counter
getcontext().prec = 100

MOD = 10**9 + 7
INF = float("+inf")

if sys.subversion[0] != "CPython":  # PyPy?
    raw_input = lambda: sys.stdin.readline().rstrip()
pr = lambda *args: sys.stdout.write(" ".join(str(x) for x in args) + "\n")
epr = lambda *args: sys.stderr.write(" ".join(str(x) for x in args) + "\n")
die = lambda *args: pr(*args) ^ exit(0)

read_str = raw_input
read_strs = lambda: raw_input().split()
read_int = lambda: int(raw_input())
read_ints = lambda: map(int, raw_input().split())
read_float = lambda: float(raw_input())
read_floats = lambda: map(float, raw_input().split())

"---------------------------------------------------------------"

N, M, K = read_ints()
s = read_str()
t = read_str()

for off in xrange(1, len(s) + 1):
    a = s[off:]
    if a == s[:len(a)]:
        break
else:
    assert 0

alphanum = {c:ascii_lowercase.index(c) for c in ascii_lowercase}

dist = {
    (a, b): min(abs(ca - cb), abs(ca + 26 - cb), abs(cb + 26 - ca))
    for a, ca in alphanum.items()
    for b, cb in alphanum.items()
}

suflen = off
suf = s[-off:]

def calc_cost(i, w):
    if i + len(w) > len(t):
        return None
    cost = 0
    for x, y in zip(w, t[i:]):
        cost += dist[x, y]
    return cost

cost_full = [calc_cost(i, s) for i in xrange(len(t) + 1)]
cost_suf = [calc_cost(i, suf) for i in xrange(len(t) + 1)]
# pr(dist['c', 'b'])
# pr(dist['b', 'c'])
#pr(cost_full)
#pr(cost_suf)
dp = [{} for i in xrange(len(t) + 1)]
dp[len(t)][0] = 0
# dp[pos][num_occur] = cost

ans = 0
for i in reversed(range(len(t))):
    dpcur = dp[i] = dp[i+1].copy()
    pos = i + len(s)
    num1 = 1
    cost1 = cost_full[i]
    while pos <= len(t):
        for num2, cost2 in dp[pos].items():
            num = num1 + num2
            cost = cost1 + cost2
            if cost > K:
                continue
            ans = max(ans, num)
            if num not in dpcur:
                dpcur[num] = cost
            else:
                dpcur[num] = min(dpcur[num], cost)
        pos += suflen
        if pos > len(t):
            break
        num1 += 1
        cost1 += cost_suf[pos - suflen]

print ans