@staticmethod
def c():
    (h, w, t) = map(int, sys.stdin.readline().split())
    s = [list(s) for s in sys.stdin.read().split()]
    for i in range(h):
        for j in range(w):
            if (s[i][j] == 'S'):
                (sy, sx) = (i, j)
            if (s[i][j] == 'G'):
                (gy, gx) = (i, j)
    s[sy][sx] = s[gy][gx] = '.'
    (source, target) = ((sy, sx), (gy, gx))

    def heuristic_function(u, v=target):
        return (abs((v[0] - u[0])) + abs((v[1] - u[0])))

    def min_time(x):
        'my lib'
        graph = GeometryTopology.Graph()
        for i in range(h):
            for j in range(w):
                graph.add_node((i, j))
        for i in range(h):
            for j in range(w):
                if (i > 0):
                    graph.add_edge((i, j), ((i - 1), j), weight=(1 if (s[(i - 1)][j] == '.') else x))
                if (i < (h - 1)):
                    graph.add_edge((i, j), ((i + 1), j), weight=(1 if (s[(i + 1)][j] == '.') else x))
                if (j > 0):
                    graph.add_edge((i, j), (i, (j - 1)), weight=(1 if (s[i][(j - 1)] == '.') else x))
                if (j < (w - 1)):
                    graph.add_edge((i, j), (i, (j + 1)), weight=(1 if (s[i][(j + 1)] == '.') else x))
        return graph.dijkstra(source)[target]
        'networkx'
        graph = nx.DiGraph()
        for i in range(h):
            for j in range(w):
                if (i > 0):
                    graph.add_edge((i, j), ((i - 1), j), weight=(1 if (s[(i - 1)][j] == '.') else x))
                if (i < (h - 1)):
                    graph.add_edge((i, j), ((i + 1), j), weight=(1 if (s[(i + 1)][j] == '.') else x))
                if (j > 0):
                    graph.add_edge((i, j), (i, (j - 1)), weight=(1 if (s[i][(j - 1)] == '.') else x))
                if (j < (w - 1)):
                    graph.add_edge((i, j), (i, (j + 1)), weight=(1 if (s[i][(j + 1)] == '.') else x))
        return nx.dijkstra_path_length(graph, source, target)
        return nx.astar_path_length(graph, source, target, heuristic_function)

    def binary_search():
        (lo, hi) = (1, (t + 1))
        while ((lo + 1) < hi):
            x = ((lo + hi) // 2)
            if (min_time(x) > t):
                hi = x
            else:
                lo = x
        return lo
    print(binary_search())
@staticmethod
def c():
    (h, w, t) = map(int, sys.stdin.readline().split())
    s = [list(s) for s in sys.stdin.read().split()]
    for i in range(h):
        for j in range(w):
            if (s[i][j] == 'S'):
                (sy, sx) = (i, j)
            if (s[i][j] == 'G'):
                (gy, gx) = (i, j)
    s[sy][sx] = s[gy][gx] = '.'
    (source, target) = ((sy, sx), (gy, gx))

    def heuristic_function(u, v=target):
        return (abs((v[0] - u[0])) + abs((v[1] - u[0])))

    def min_time(x):
        'my lib'
        graph = GeometryTopology.Graph()
        for i in range(h):
            for j in range(w):
                graph.add_node((i, j))
        for i in range(h):
            for j in range(w):
                if (i > 0):
                    graph.add_edge((i, j), ((i - 1), j), weight=(1 if (s[(i - 1)][j] == '.') else x))
                if (i < (h - 1)):
                    graph.add_edge((i, j), ((i + 1), j), weight=(1 if (s[(i + 1)][j] == '.') else x))
                if (j > 0):
                    graph.add_edge((i, j), (i, (j - 1)), weight=(1 if (s[i][(j - 1)] == '.') else x))
                if (j < (w - 1)):
                    graph.add_edge((i, j), (i, (j + 1)), weight=(1 if (s[i][(j + 1)] == '.') else x))
        return graph.dijkstra(source)[target]
        'networkx'
        graph = nx.DiGraph()
        for i in range(h):
            for j in range(w):
                if (i > 0):
                    graph.add_edge((i, j), ((i - 1), j), weight=(1 if (s[(i - 1)][j] == '.') else x))
                if (i < (h - 1)):
                    graph.add_edge((i, j), ((i + 1), j), weight=(1 if (s[(i + 1)][j] == '.') else x))
                if (j > 0):
                    graph.add_edge((i, j), (i, (j - 1)), weight=(1 if (s[i][(j - 1)] == '.') else x))
                if (j < (w - 1)):
                    graph.add_edge((i, j), (i, (j + 1)), weight=(1 if (s[i][(j + 1)] == '.') else x))
        return nx.dijkstra_path_length(graph, source, target)
        return nx.astar_path_length(graph, source, target, heuristic_function)

    def binary_search():
        (lo, hi) = (1, (t + 1))
        while ((lo + 1) < hi):
            x = ((lo + hi) // 2)
            if (min_time(x) > t):
                hi = x
            else:
                lo = x
        return lo
    print(binary_search())