class Solution:
    def orderOfLargestPlusSign(self, N, mines):
        # left, up, right, down

        mines = {(i, j) for i,j in mines}
        dp = [[[0, 0, 0, 0] for i in range(N)]for j in range(N)]
        for i in range(N):
            if (i, 0) not in mines:
                dp[i][0] = [1, 1, 1, 1]
            if (0, i) not in mines:
                dp[0][i] = [1, 1, 1, 1]
        for i in range(N):
            if (i, N-1) not in mines:
                dp[i][N-1] = [1, 1, 1, 1]
            if (N-1, i) not in mines:
                dp[N-1][i] = [1, 1, 1, 1]

        for i in range(1, N):
            for j in range(1, N):
                if (i,j) not in mines:
                    dp[i][j][0] = dp[i][j-1][0] + 1
                    dp[i][j][1] = dp[i-1][j][1] + 1


        for i in range(N-2, -1, -1):
            for j in range(N-2, -1, -1):
                if (i,j) not in mines:
                    dp[i][j][2] = dp[i][j + 1][2] + 1
                    dp[i][j][3] = dp[i + 1][j][3] + 1
        res = 0
        for i in range(N):
            for j in range(N):
                res = max(res, min(dp[i][j]))
        return res