소프티어

import sys

from collections import deque

from itertools import product

N, M = map(int, sys.stdin.readline().split())

num_list = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

visted = [[False] * N for _ in range(N)]

pos_idx = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def bfs_all_paths(x, y):

  q = deque()

  q.append((x, y, 0, [(x, y)], {(x, y)}, num_list[x][y])) # (x좌표, y좌표, 시간, 경로, 방문집합, 누적수확량)

  results = []

  while q:

    cx, cy, time, path, visited, total = q.popleft()

    results.append((path, visited, total))

    if time == 3:

      continue

    for dx, dy in directions:

      nx, ny = cx + dx, cy + dy

      if 0 <= nx < N and 0 <= ny < N and (nx, ny) not in visited:

        q.append((nx, ny, time + 1, path + [(nx, ny)], visited | {(nx, ny)}, total + num_list[nx][ny]))

  return results

all_paths = []

for xi, yi in pos_idx:

  all_paths.append(bfs_all_paths(xi - 1, yi - 1)) # 0-indexed

# 가능한 모든 경로 조합에서 최대 수확량 계산

max_total = 0

for combo in product(*all_paths):

  time_step_map = {} # key: 시간, value: 해당 시간에 있는 위치 집합

  valid = True

  collected = set()

  total = 0

  for path, visited, _ in combo:

    for t, pos in enumerate(path):

      if t not in time_step_map:

        time_step_map[t] = set()

      if pos in time_step_map[t]: # 같은 시간에 같은 위치면 충돌

        valid = False

        break

    collected |= visited # 전체 수확 위치

  total = sum(num_list[x][y] for x, y in collected)

  max_total = max(max_total, total)

print(max_total)