#include <queue>
#include <fstream>
using namespace std;
ifstream fin("taxe2.in");
ofstream fout("taxe2.out");
int s,ss,n;
short A[111][111],B[111][111];
typedef struct coada
{
    short l;
    short c;
} COADA;
short p1[]= {0,1,-1,0,0};
short p2[]= {0,0,0,1,-1};
COADA x,y,aux;
queue <COADA> Q;
short inc,sf;
void lee()
{
    aux.l=aux.c=1;
    Q.push(aux);
    B[1][1]=A[1][1];
    while (!Q.empty())
    {
        x=Q.front();
        Q.pop();
        for (int k=1; k<=4; k++)
        {
             if(B[x.l+p1[k]][x.c+p2[k]]==0)
             {
                 B[x.l+p1[k]][x.c+p2[k]]=B[x.l][x.c]+A[x.l+p1[k]][x.c+p2[k]];
                 y.l=x.l+p1[k];
                 y.c=x.c+p2[k];
                 Q.push(y);
            }
            else
                if(B[x.l][x.c]+A[x.l+p1[k]][x.c+p2[k]]<B[x.l+p1[k]][x.c+p2[k]])
            {
                 B[x.l+p1[k]][x.c+p2[k]]=B[x.l][x.c]+A[x.l+p1[k]][x.c+p2[k]];
                 y.l=x.l+p1[k];
                 y.c=x.c+p2[k];
                 Q.push(y);
            }
        }
    }

}
int main()
{
    fin>>s>>n;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            fin>>A[i][j];
    for (int i=0; i<=n+1; i++)
    {
        B[0][i]=-10;
        B[n+1][i]=-10;
        B[i][0]=-10;
        B[i][n+1]=-10;
    }
    lee();
    if (s-B[n][n]>=0)
        fout<<s-B[n][n];
    else
        fout<<-1;
    return 0;
}