소프티어

import sys
from itertools import permutations

input = sys.stdin.readline
n, m = map(int, input().rstrip().split())

M = [list(map(int, input().rstrip().split())) for _ in range(n)]
positions = [list(map(int, input().rstrip().split())) for _ in range(m)]

ans = 0
def dfs(x, y, used, res, cnt):

  used.add((x,y))

  if cnt == 0: return (used, res+M[x][y])
  u0, r0 = dfs(x-1, y, used.copy(), res+M[x][y], cnt-1) if 0<=x-1<n and 0<=y<n and (x-1, y) not in used else (set(), 0)
  u1, r1 = dfs(x+1, y, used.copy(), res+M[x][y], cnt-1) if 0<=x+1<n and 0<=y<n and (x+1, y) not in used else (set(), 0)
  u2, r2 = dfs(x, y-1, used.copy(), res+M[x][y], cnt-1) if 0<=x<n and 0<=y-1<n and (x, y-1) not in used else (set(), 0)
  u3, r3 = dfs(x, y+1, used.copy(), res+M[x][y], cnt-1) if 0<=x<n and 0<=y+1<n and (x, y+1) not in used else (set(), 0)
  tmpRes = [r0, r1, r2, r3]
  tmpUsed = [u0, u1, u2, u3]
  idx = tmpRes.index(max(tmpRes))

  return (tmpUsed[idx], tmpRes[idx])

perms = permutations([i for i in range(m)])
for perm in perms:
  res = 0
  visited = set()
  for i in perm:
    (x, y) = (positions[i][0]-1, positions[i][1]-1)
    tmpUsed, tmpRes = dfs(x, y, visited, 0, 3)
    visited = visited.union(tmpUsed)
    res += tmpRes
  ans = max(ans, res)

print(ans)

마지막 테스트 케이스만 실패하는데 도저히 모르겠어요. 전제조건 3번째 '1<=수확량<=1000' 이거 인가 싶어서 각 시도에서 총 수확량이 1000을 벗어나는 경우 제외해봤는데 오히려 더 많은 오답이 나오구요. 조언 부탁드립니다ㅠ