#include <vector>
#include <fstream>
#include <iostream>
#include <queue>
#include <algorithm>
#define MAX 105

using namespace std;

ifstream in("taxe2.in");
ofstream out("taxe2.out");

int di[4] = {0,0,1,-1};
int dj[4] = {1,-1,0,0};

queue < pair < int , int > > myQueue;

int Map[MAX][MAX];
int SecondMap[MAX][MAX];
bool beenThere[MAX][MAX];

int Euro, N;

void Read()
{
    in >> Euro >> N ;

    for ( int i = 1; i <= N ; ++i)
        for ( int j = 1; j <= N ; ++j)
    {
        int x;
        in >> x;
        Map[i][j] = x;
        SecondMap[i][j]= 10000;
    }
}

bool Inside(int i , int j)
{
    if(i < 1 || j < 1 || i > N || j > N)
        return false;

        if( beenThere[i][j] == true)
            return false;

    return true;
}

void Lee()
{
    myQueue.push(make_pair(1,1));
    SecondMap[1][1] = Map[1][1];

    while(!myQueue.empty())
    {
        int i = myQueue.front().first;
        int j = myQueue.front().second;
        beenThere[i][j] = true;

        myQueue.pop();

        for(int direction = 0 ; direction < 4 ; ++direction)
            {
                int i_next = i +di[direction];
                int j_next = j + dj[direction];

                if(Inside(i_next,j_next) &&  SecondMap[i][j] + Map[i_next][j_next] < SecondMap[i_next][j_next])
                {
                    SecondMap[i_next][j_next] = SecondMap[i][j] + Map[i_next][j_next];
                    myQueue.push(make_pair(i_next,j_next));
                }
            }



    }



}

void Rezolv()
{

    Lee();

    int Raspuns = SecondMap[N][N];

    if(Raspuns > Euro) cout<< -1;
    else cout << Euro-Raspuns;

}


int main()
{
    Read();
    Rezolv();


}