#include<stdio.h>


FILE *f,*g;

int a[100][100];
int coadax[10000],coaday[10000];

int main()
{
	int s,n,i,j,p,u,coadamin,xv,yv,xv1,yv1;
	f=fopen("taxe.in","r");
	g=fopen("taxe.out","w");
	fscanf(f,"%d",&s);
	fscanf(f,"%d",&n);

	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			fscanf(f,"%d",&a[i][j]);



	int dx[]={-1,0};
	int dy[]={0,-1};          //pornesc de la punctul de oprire
	p=0;
	u=0;
	coadax[0]=n;            //punctele din matrie
	coaday[0]=n;
	coadamin=a[n][n];   //tin minte minimul platit pana in acel punct
	while(p<=u)
	{


		xv=coadax[p]+dx[0];
		yv=coaday[p]+dy[0];
		xv1=coadax[p]+dx[1];
		yv1=coaday[p]+dy[1];
		if((xv<1||yv<1)&&(xv1<1||yv1<1))
			p=u+1;
		if((xv<1||yv<1)&&(xv1>0&&yv1>0))
		{
			u++;
			coadax[u]=xv1;
			coaday[u]=yv1;
			coadamin=coadamin+a[xv1][yv1];
		}
		else
		{
			if((xv1<1||yv1<1)&&(xv>0&&yv>0))
			{
				u++;
				coadax[u]=xv;
				coaday[u]=yv;
				coadamin=coadamin+a[xv][yv];
			}
			else
			{
				if(a[xv][yv]<a[xv1][yv1])
				{
					u++;
					coadax[u]=xv;
					coaday[u]=yv;
					coadamin=coadamin+a[xv][yv];
				}
				else
				{
					u++;
					coadax[u]=xv1;
					coaday[u]=yv1;
					coadamin=coadamin+a[xv1][yv1];
				}
			}
		}
		p++;
	}
	if(s-coadamin>=0)
		fprintf(g,"%d",s-coadamin);
	else
		fprintf(g,"%d",-1);
	fprintf(g,"\n");
	fcloseall();
	return 0;

}