[코드트리] 코드트리 빵

import sys
import heapq
from collections import deque
input = sys.stdin.readline

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

def find_basecamp(x, y):
    queue = deque([]); queue.append((x, y))
    visit = [[-1]*N for n in range(N)]; visit[x][y] = 0

    candi = []
    while queue:
        x, y = queue.popleft()
        if board[x][y] == 1: heapq.heappush(candi, (visit[x][y], x, y))
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0<=nx<N and 0<=ny<N:
                if visit[nx][ny] == -1 and board[nx][ny] != 2:
                    queue.append((nx, ny))
                    visit[nx][ny] = visit[x][y] + 1
    m_camp = heapq.heappop(candi)
    return m_camp[1:]

def find_shortest(src_x, src_y, dest_x, dest_y):
    queue = deque([]); queue.append((src_x, src_y, -1, -1))
    visit = [[False]*N for n in range(N)]; visit[src_x][src_y] = True

    while queue:
        x, y, fx, fy = queue.popleft()
        if (x, y) == (dest_x, dest_y): return [fx, fy]
        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] != 2:
                    if fx==-1 and fy==-1: queue.append((nx, ny, nx, ny))
                    else: queue.append((nx, ny, fx, fy))
                    visit[nx][ny] = True

N, M = map(int, input().split())
board = [list(map(int, input().split())) for n in range(N)] #0: 빈칸, 1: 베이스 캠프, 2: 빨간 칸
person = dict()
for m in range(M):
    tmp = list(map(int, input().split()))
    person[m+1] = [-1, -1, tmp[0]-1, tmp[1]-1] #[cx, cy, gx, gy]

curtime = 1; finished_person = set()
while True:
    ##### 1번 수행 (편의점을 방향을 향해 1칸 이동)
    for p in person.keys():
        if p not in finished_person and person[p][0] != -1 and person[p][1] != -1:
            cx, cy, gx, gy = person[p]
            cx, cy = find_shortest(cx, cy, gx, gy)
            person[p][0] = cx; person[p][1] = cy

    ##### 2번 수행 (편의점에 도착한 경우 처리)
    for p in person.keys():
        cx, cy, gx, gy = person[p]
        if (cx, cy) == (gx, gy):
            board[cx][cy] = 2
            finished_person.add(p)
    
    ##### 3번 수행 (격자 밖에 있다면, 베이스 캠프에 들어가기)
    for p in person.keys():
        if person[p][0] == -1 and person[p][1] == -1 and p == curtime:
            bx, by = find_basecamp(person[p][2], person[p][3])
            board[bx][by] = 2
            person[p][0] = bx; person[p][1] = by

    if len(finished_person) == M: break
    curtime += 1
    
print(curtime)