[코드트리] 꼬리잡기놀이

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
board = [list(map(int, input().split())) for n in range(N)]

dx = (0, -1, 0, 1)
dy = (1, 0, -1, 0)

def preproc_line(x, y, team_num):
    line[(x, y)] = team_num
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if 0<=nx<N and 0<=ny<N:
            if not visit[nx][ny] and board[nx][ny] >= 1 and board[nx][ny] <= 4:
                visit[nx][ny] = True
                preproc_line(nx, ny, team_num)

def preproc_person(x, y, th):
    if line[(x, y)] in person: person[line[(x, y)]].append([th, -1, x, y])
    else: person[line[(x, y)]] = [[th, -1, x, y]]
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if 0<=nx<N and 0<=ny<N:
            if not visit[nx][ny] and board[nx][ny] != 4:
                if (board[nx][ny] == board[x][y]+1) or (board[nx][ny] == board[x][y]):
                    visit[nx][ny] = True
                    preproc_person(nx, ny, th+1)

def move_person():
    for team_num in person.keys():
        ### 1번만 먼저 이동
        x, y = person[team_num][0][2], person[team_num][0][3]
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0<=nx<N and 0<=ny<N:
                if board[nx][ny] == 4:
                    if (nx, ny) != (person[team_num][1][2], person[team_num][1][3]): break
        person[team_num][0][2] = nx; person[team_num][0][3] = ny

        px=x; py=y
        for i in range(1, len(person[team_num])):
            tx=person[team_num][i][2]; ty=person[team_num][i][3]
            person[team_num][i][2]=px; person[team_num][i][3]=py
            px=tx; py=ty

def throw_ball(k):
    global total_score

    ### 공 방향 설정
    k = k%(4*N)
    d = (k)//N; n = (k)%N
    ball = []
    if d == 0: ball = [n, 0]
    elif d == 1: ball = [N-1, n]
    elif d == 2: ball = [N-n-1, N-1]
    else: ball = [0, N-n-1]

    ### 공 던지기
    changed_team = -1; flag = False
    for i in range(N):
        x, y = ball
        if flag: break
        if (x, y) in line:
            team_num = line[(x, y)]
            for i in range(len(person[team_num])):
                if (x, y) == (person[team_num][i][2], person[team_num][i][3]):
                    total_score += person[team_num][i][0]**2
                    changed_team = team_num
                    flag = True
                    break
        ball[0] = x+dx[d]; ball[1] = y+dy[d]
    
    ### 머리 꼬리 바꾸기
    if changed_team != -1:
        for i in range(len(person[changed_team])):
            th, n, x, y = person[changed_team][i]
            person[changed_team][i][0] = n - th + 1
        person[changed_team].sort()

line = dict() ### {(x, y): team_num, ...} ###
visit = [[False]*N for n in range(N)]; team_num = 1
for i in range(N):
    for j in range(N):
        if board[i][j] <= 4 and board[i][j] >= 1 and not visit[i][j]:
            visit[i][j] = True
            preproc_line(i, j, team_num)
            team_num += 1

person = dict() ### {team_num: [[몇번째, 인원수, x, y], ...], ...} ###
visit = [[False]*N for n in range(N)]
for i in range(N):
    for j in range(N):
        if board[i][j] == 1:
            visit[i][j] = True
            preproc_person(i, j, 1)
for team_num in person.keys():
    P = len(person[team_num])
    for i in range(P): person[team_num][i][1] = P

for i in range(N):
    for j in range(N):
        if board[i][j] <= 3 and board[i][j] >= 1: board[i][j] = 4

total_score = 0
for k in range(K):
    move_person()
    throw_ball(k)
print(total_score)