#include <iostream>
#include <fstream>
using namespace std;
int di[4]={0,1,-1,0};
int dj[4]={1,0,0,-1};
int a[101][101];
int n,s,inc,i,j,banif;
ifstream ci("taxe2.in");
ofstream cou("taxe2.out");
struct milcorupidemilinvinetesti
{
    int x,y;
};
milcorupidemilinvinetesti q[50000];
int ok(int i,int j)
{
    if(i<1 or j<1 or i>n or j>n )
        return 0;
    return 1;

}
void millee()
{
    int ii,jj,sf=1;
    inc=0;
    while(inc<=sf)
    {
        i=q[++inc].x;
        j=q[inc].y;
        for(int k=0;k<4;k++)
        {
            ii=i+di[k];
            jj=j+dj[k];

            if(ok(ii,jj))
            {
                if(a[i][j]-a[ii][jj]>a[ii][jj])
                {
                    a[ii][jj]=a[i][j]-a[ii][jj];
                    q[++sf].x=ii;
                    q[sf].y=jj;
                }
            }

        }

    }

}
int main()
{
    ci>>s>>n;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            ci>>a[i][j];
    a[1][1]=s;
    q[1].x=1;
    q[1].y=1;
    banif=a[n][n];
    millee();
    if(a[n][n]==banif)
        cou<<-1;
    else
    cou<<a[n][n];

}