#include <bits/stdc++.h>
using namespace std;
int matrix[501][501];
bool verified[501][501];
int distances[501][501];
int dx[4]={1, 0, -1, 0};
int dy[4]={0, -1, 0, 1};
deque <pair<int,int>> coada;
queue <pair<int,int>> C;
int isInside(int x, int y, int n, int m){
    return 1<=x and x<=n and 1<=y and y<=m;}
void leeAlg(int g, int n, int m){
    distances[1][1]=0;
    coada.push_front({1, 1});
    while(coada.size()){
       pair <int, int> Element=coada.front();
       coada.pop_front();
       int currentx=Element.first;
       int currenty=Element.second;
       for(int i=0; i <= 3; i++){
            int newx=currentx+dx[i];
            int newy=currenty+dy[i];
            if(verified[newx][newy]==true)
                continue;
            if(isInside(newx, newy, n, m)==false)
                continue;
            if(matrix[newx][newy]<g){
                distances[newx][newy]=distances[currentx][currenty]+1;
                coada.push_back({newx, newy});
            }
            else {
                    coada.push_front({newx, newy});
                    distances[newx][newy]=distances[currentx][currenty];
            }
            verified[newx][newy]=true;
        }
    }
}
bool lee2(int g, int n, int m){
    for(int i=1; i <= n; i++)
        for(int j=1; j <= m; j++){
            verified[i][j]=0;
            distances[i][j]=0;
        }
    C.push({1,1});
    while(C.size()){
        pair<int, int> elem=C.front();
        C.pop();
        int acmx=elem.first;
        int acmy=elem.second;
        for(int i=1; i <= 3; i++){
            int noux=acmx+dx[i];
            int nouy=acmy+dy[i];
            if(isInside(noux, nouy, n, m) && verified[noux][nouy]==false ){
                if(matrix[noux][nouy]>=g){
                    distances[noux][nouy]=1;
                    verified[noux][nouy]=1;
                    C.push({noux, nouy});
                }
                else verified[noux][nouy]=1;
            }
        }
    }
    return distances[n][n];
}
int cautbin(int n){
    int st=0, dr=5000, mij=0;
    while(st<dr){
        mij=(st+dr+1)/2;
        if(lee2(mij, n, n))
            st=mij;
        else dr=mij-1;
    }
    return st;
}
ifstream fin("rover.in");
ofstream fout("rover.out");
int main()
{
    int v, n, g;
    fin >> v >> n ;
    if(v==1)
        fin >> g;
    for(int i=1; i <= n; i++)
        for(int j=1; j <= n; j++)
            fin >> matrix[i][j];
    if(v==1){
        leeAlg(g, n, n);
        fout << distances[n][n];
    }
    else{
        fout << cautbin(n);
    }
    return 0;
}