#include <iostream>
#include <fstream>
#include <queue>
using namespace std;

const int NMAX=103;

int dy[4]={0, 0, -1, 1};
int dx[4]={-1, 1, 0, 0};

ifstream fin("taxe2.in");
ofstream fout("taxe2.out");
queue <pair <int , int> > Q;

int H[NMAX][NMAX], Lee[NMAX][NMAX];
int S, n, dif;

bool OK(int i, int j){
    if(i<0 || j<0 || i>=n || j>=n)
        return false;
}

int read(){
    fin >> S >> n;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            fin >> H[i][j];
}

/*void afisare_matrice(int matrice[NMAX][NMAX]){
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cout << matrice[i][j];
            if(matrice[i][j]>=10 || matrice[i][j]<0)
                cout << ' ';
            else
                cout << "  ";
        }
        cout << endl;
    }
}*/

int lee(){
    int i, j, i_1, j_1;
    Lee[0][0]=H[0][0];
    Q.push(make_pair(0, 0));
    while(!Q.empty()){
        i = Q.front().first;
        j = Q.front().second;
        for(int d=0; d<4; d++){
            i_1 = i + dy[d];
            j_1 = j + dx[d];
            if(OK(i_1, j_1)){
                if(!Lee[i_1][j_1]){
                    Lee[i_1][j_1]=Lee[i][j]+H[i_1][j_1];
                    Q.push(make_pair(i_1, j_1));
                } else if(Lee[i][j]+H[i_1][j_1]<Lee[i_1][j_1]){
                    Lee[i_1][j_1]=Lee[i][j]+H[i_1][j_1];
                    Q.push(make_pair(i_1, j_1));
                }
            }
        }
        Q.pop();
    }
}

int main() {
    read();
    lee();
    dif=S-Lee[n-1][n-1];
    fout << dif;
    //afisare_matrice(Lee);
}