#include <cstdio>
#include <queue>
#define dim 101
#define INF 10000;
using namespace std;
bool viz[dim][dim];
int sum,i,n,j,l,c,u,p,x,y;
short q[2][8*dim*dim];
short mat[dim][dim];
short cost[dim][dim];
const short int dx[4]={0,1,0,-1};
const short int dy[4]={1,0,-1,0};
FILE *fin=fopen("taxe2.in","r"), *fout=fopen("taxe2.out","w");
int main()
{
    fscanf(fin,"%hd%hd",&sum,&n);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            fscanf(fin,"%hd",&mat[i][j]);
            cost[i][j]=INF;
        }
    cost[1][1]=mat[1][1];
    q[0][1]=1;
    q[1][1]=1;
    u=p=1;
    while(p<=u)
    {
        x=q[0][p];
        y=q[1][p];
        viz[x][y]=0;
        if(cost[n][n]>cost[x][y])
            for(i=0;i<4;i++)
            {
                l=x+dx[i];
                c=y+dy[i];
                if(l>=1&&l<=n&&c>=1&&c<=n&&cost[x][y]+mat[l][c]<cost[l][c]&&cost[n][n]>cost[x][y]+mat[l][c])
                {
                    cost[l][c]=cost[x][y]+mat[l][c];
                    if(!viz[l][c])
                    {
                        viz[l][c]=1;
                        q[0][++u]=l;
                        q[1][u]=c;
                    }
                }
            }
        p++;
    }
    if(cost[n][n]>sum)
        fprintf(fout,"%hd",-1);
    else
        fprintf(fout,"%hd",sum-cost[n][n]);
    return 0;
}