#include <fstream>
using namespace std;
ifstream f("taxe2.in");
ofstream g("taxe2.out");
int S,b[102][102];
short a[102][102],n,i,j,dx[]={1,0,-1,0},dy[]={0,1,0,-1};
struct punct
{
    short x,y;
}c[100001];
void citire()
{
    f>>S>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            f>>a[i][j];
}
void lee()
{
    int p,u,i,x1,y1;
    for(i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        b[i][j]=2010000;
    punct v;
    c[1].x=1;
    c[1].y=1;
    p=u=1;
    b[1][1]=a[1][1];
    while(p<=u)
    {
        v=c[p];
        for(i=0;i<4;i++)
        {
            x1=v.x+dx[i];
            y1=v.y+dy[i];
            if((b[x1][y1]>a[x1][y1]+b[v.x][v.y]) && x1>=1 && y1>=1 && x1<=n && y1<=n)
            {
                b[x1][y1]=a[x1][y1]+b[v.x][v.y];
                c[++u].x=x1;
                c[u].y=y1;
            }
        }
        p++;
    }
}
int main()
{
    citire();
    lee();
    if(S-b[n][n]>=0) g<<S-b[n][n];
    else g<<-1;
}