[白俊]19237大人サメ

import java.util.Scanner;

public class Main {
    public static class Shark {
        int x, y, d, live;

        public Shark(int x, int y, int d, int live) {
            this.x = x;
            this.y = y;
            this.d = d;
            this.live = live;
        }
    }

    public static int N, M, K;
    public static Shark[] sharks = new Shark[401];
    public static int[][][] sharkDir = new int[401][5][4];
    public static int[][][] map = new int[20][20][2];  // 0: 냄새 번호, 1: 냄새 남은 시간

    public static int[] dx = {0, -1, 1, 0, 0};
    public static int[] dy = {0, 0, 0, -1, 1};

    //끝났는지 확인
    public static boolean isEnd() {
        for (int i = 1; i <= M; i++) {
            if ( i != 1 && sharks[i].live == 1)
                return false;
        }
        return true;
    }

    //상어 이동
    public static void sharkMove() {
        for (int i = 1; i <= M; i++) {
            //죽은 상어 제외
            if (sharks[i].live == 0) continue;
            //우선 순위에 따라 진행
            int curDir = sharks[i].d;
            boolean ExistEmpty = false;
            //1. 빈칸 찾기
            for (int j = 0; j < 4; j++) {
                int X = sharks[i].x + dx[sharkDir[i][curDir][j]];
                int Y = sharks[i].y + dy[sharkDir[i][curDir][j]];
                if (X < 0 || Y < 0 || X >= N || Y >= N) continue;
                //빈 칸이었으면
                if (map[X][Y][0] == 0 || map[X][Y][1] == -1) {
                    ExistEmpty = true;
                    //다른 상어도 방금 들어왔을때 -> 현재 들어가는 상어 바로 죽임
                    if (map[X][Y][0] != 0) {
                        sharks[i].live = 0;
                    }
                    //그냥 빈칸일때 -> 들어가고 냄새남김
                    else {
                        map[X][Y][0] = i;
                        map[X][Y][1] = -1;
                        sharks[i].x = X;
                        sharks[i].y = Y;
                        sharks[i].d = sharkDir[i][curDir][j];
                    }
                    break;
                }
            }

            //2. 내 냄새 찾기
            if (ExistEmpty) continue;
            for (int j = 0; j < 4; j++) {
                int X = sharks[i].x + dx[sharkDir[i][curDir][j]];
                int Y = sharks[i].y + dy[sharkDir[i][curDir][j]];
                if (X < 0 || Y < 0 || X >= N || Y >= N) continue;
                //내 냄새라면
                if (map[X][Y][0] == i) {
                    map[X][Y][1] = K+1;
                    sharks[i].x = X;
                    sharks[i].y = Y;
                    sharks[i].d = sharkDir[i][curDir][j];
                    break;
                }
            }
        }
        //빈칸 부분 정상화
        for (int a = 0; a < N; a++)
            for (int b = 0; b < N; b++)
                if (map[a][b][1] == -1) map[a][b][1] = K+1;
    }

    //냄새 시간 줄여주기
    public static void smellProcess() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j][0] != 0) {
                    if (--map[i][j][1] == 0)
                        map[i][j][0] = 0;
                }
            }
        }
    }

    //시뮬레이션 시작
    public static void simulate() {
        int result = 0;
        //하루씩 늘려줌
        while(true) {
            result++;
            if (result == 1001) {
                System.out.println(-1);
                return;
            }
            sharkMove();
            if (isEnd()) {
                System.out.println(result);
                return;
            }
            smellProcess();
        }
    }

    public static void input() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); M = sc.nextInt(); K = sc.nextInt();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int num = sc.nextInt();
                if (num == 0) continue;
                sharks[num] = new Shark(i, j, 0, 1);
                map[i][j][0] = num;
                map[i][j][1] = K;
            }
        }
        for (int i = 1; i <= M; i++)
            sharks[i].d = sc.nextInt();
        for (int i = 1; i <= M; i++) {
            for (int j = 1; j <= 4; j++) {
                for (int k = 0; k < 4; k++)
                    sharkDir[i][j][k] = sc.nextInt();
            }
        }
    }

    public static void main(String[] args) {
        input();
        simulate();
    }
}