88B - Keyboard - CodeForces Solution

'''Author : seraph14'''
from cmath import isclose
from collections import defaultdict
import math
import sys, io, os
import heapq
if 'PyPy' in sys.version:
    from _continuation import continulet
else:
    import threading
input = sys.stdin.readline

hqp = heapq.heappop
hqs = heapq.heappush

def _print(*argv, sep=" "):
    sys.stdout.write(sep.join(map(str, argv)) + "\n")

def inp():
    return (int(input()))

def inlt():
    return (list(map(int, input().split())))

def insr():
    if input == sys.stdin.readline:
        s = input()
        return list(s.strip())
    else:
        s = input().decode()
        return (list(s[:len(s)-2]))

def invr():
    return (map(int, input().split()))

def get_bool(right):
    return "YES" if right else "NO"

def solve():
    pass

def main():
    n, m, x = invr()
    keyboard = []
    for _ in range(n):
        keyboard.append(insr())
    q = inp()
    T = insr()

    key_to_coord = defaultdict(list)
    key_to_dist = defaultdict(float)
    
    for i in range(n):
        for j in range(m):
            key_to_coord[keyboard[i][j]].append((i, j))
    
    for t in key_to_coord:
        if t == "S":
            continue
        min_cost = float("inf")
        for x1, y1 in key_to_coord[t]:
            if "S" not in key_to_coord:
                break
            for x2, y2 in key_to_coord["S"]:
                min_cost = min(min_cost, (x1-x2)**2 + (y1-y2)**2)
        key_to_dist[t] = math.sqrt(min_cost) if min_cost != float("inf") else float("inf")
    
    cost = 0
    for t in T:
        if (t.islower() and t not in key_to_coord) or (t.isupper() and t.lower() not in key_to_coord):
            _print(-1)
            return
        if t.islower():
            continue
            
        if "S" not in key_to_coord:
            _print(-1)
            return
        val = key_to_dist[t.lower()]
        cost += 0 if math.isclose(val, x) or val < x else 1
    _print(cost)


if __name__ == '__main__':
    if 'PyPy' in sys.version:

        def bootstrap(cont):
            call, arg = cont.switch()
            while True:
                call, arg = cont.switch(
                    to=continulet(lambda _, f, args: f(*args), call, arg))
        cont = continulet(bootstrap)
        cont.switch()
        main()
    else:
        sys.setrecursionlimit(1 << 30)
        threading.stack_size(1 << 27)

        main_thread = threading.Thread(target=main)
        main_thread.start()
        main_thread.join()