#include <iostream>
#include <queue>
#include <algorithm>
#include <utility>

struct solve {
    int x, y, d, v;
    solve(int x1, int y1, int d1, int v1)
    : x(x1), y(y1), d(d1), v(v1)
    {
    }
};

int bfs (int xi, int yi, int xf, int yf, int lobos, int n, char mat[102][102], bool visitado[102][102])
{
    std::queue<solve> cola;
    solve temp(xi, yi, 0, lobos);
    cola.push(temp);

    while (!cola.empty( )) {
        solve actual = cola.front( );
        cola.pop( );

        if (actual.x == xf && actual.y == yf) {
            return actual.d;
        }
        if (visitado[actual.x][actual.y]) {
            continue;
        }
        visitado[actual.x][actual.y] = true;

        std::pair<int, int> vecinos[4] = {
            { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 }
        };

        for (int i = 0; i < 4; ++i) {
            int x = actual.x + vecinos[i].first;
            int y = actual.y + vecinos[i].second;

            if (x >= 0 && x < n && y >= 0 && y < n && mat[x][y] != '#' && actual.v >= 0) {
                if (mat[x][y] == '*') {
                    solve test(x, y, actual.d + 1, actual.v - 1);
                    cola.push(test);
                } else {
                    solve test(x, y, actual.d + 1, actual.v);
                    cola.push(test);
                }
            }
        }
    }

    return -1;
}

int main ( )
{
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int l, n;
    std::cin >> l >> n;

    int xi, yi, xf, yf;
    char mat[102][102];
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cin >> mat[i][j];
            if (mat[i][j] == 'E') {
                xi = i;
                yi = j;
            } else if (mat[i][j] == 'S') {
                xf = i;
                yf = j;
            }
        }
    }

    bool visitado[102][102];
    std::fill(&visitado[0][0], &visitado[0][102], false);

    int res = bfs(xf, yf, xi, yi, l, n, mat, visitado);
    std::cout << res << std::endl;
}