from collections import deque
import itertools

def get_shortest_path(grid, N):
    start = None
    end = None
    for i in range(N):
        for j in range(N):
            if grid[i][j] == 'S':
                start = (i, j)
            elif grid[i][j] == 'D':
                end = (i, j)

    queue = deque([(start, 0)])
    visited = {start}

    while queue:
        (x, y), dist = queue.popleft()
        if grid[x][y] == 'D':
            return dist

        for nx, ny in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
            if 0 <= nx < N and 0 <= ny < N and (nx, ny) not in visited and grid[nx][ny] != 'T':
                visited.add((nx, ny))
                queue.append(((nx, ny), dist + 1))
    return float('inf')

def get_sheets(grid, N, M):
    sheets = []
    for i in range(0, N, M):
        for j in range(0, N, M):
            sheet = []
            for x in range(M):
                row = []
                for y in range(M):
                    row.append(grid[i+x][j+y])
                sheet.append(row)
            sheets.append(sheet)
    return sheets

def make_grid(arrangement, sheets, N, M):
    grid = [["" for _ in range(N)] for _ in range(N)]
    num_sheets = N // M

    for idx, sheet_idx in enumerate(arrangement):
        sheet = sheets[sheet_idx]
        base_i = (idx // num_sheets) * M
        base_j = (idx % num_sheets) * M

        for i in range(M):
            for j in range(M):
                grid[base_i + i][base_j + j] = sheet[i][j]
    return grid

def solve():
    N, M = map(int, input().split())
    original_grid = [list(input().strip()) for _ in range(N)]

    sheets = get_sheets(original_grid, N, M)
    num_sheets = (N // M) ** 2

    s_sheet = d_sheet = None
    for i, sheet in enumerate(sheets):
        for row in sheet:
            if 'S' in row:
                s_sheet = i
            if 'D' in row:
                d_sheet = i

    min_dist = float('inf')
    nums = list(range(num_sheets))
    nums.remove(s_sheet)
    nums.remove(d_sheet)

    for middle_perm in itertools.permutations(nums):
        arrangement = [s_sheet] + list(middle_perm) + [d_sheet]
        grid = make_grid(arrangement, sheets, N, M)
        min_dist = min(min_dist, get_shortest_path(grid, N))

    return min_dist

if name == "main":
    print(solve())

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> ids(n), costs(n);

    for (int i = 0; i < n; i++) cin >> ids[i];
    for (int i = 0; i < n; i++) cin >> costs[i];

    int budget;
    cin >> budget;

    int maxItems = 0, minCost = 0;

    for (int i = 0; i < n; i++) {
        int itemCost = costs[i];
        int quantity = budget / itemCost;

        if (quantity > 0) {
            int currentItems = 0, currentCost = 0;

            for (int j = 0; j < n; j++) {
                if (i != j && ids[i] % ids[j] == 0) {
                    currentItems += quantity;
                    currentCost += costs[j] * quantity;
                }
            }

            if (currentItems > maxItems || (currentItems == maxItems && currentCost > minCost)) {
                maxItems = currentItems;
                minCost = currentCost;
            }
        }
    }

    cout << maxItems << " " << minCost << endl;

    return 0;
}

pair<double, double> r(double px, double py, double x1, double y1, double x2, double y2) {
    double a = y2 - y1;
    double b = x1 - x2;
    double c = x2 * y1 - x1 * y2;
    double d = (a * px + b * py + c) / sqrt(a * a + b * b);
    double nx = px - 2 * d * (a / sqrt(a * a + b * b));
    double ny = py - 2 * d * (b / sqrt(a * a + b * b));
    return {nx, ny};
}

int main() {
    double ar;
    cin >> ar;

    double x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    double s = sqrt(ar);
    vector<pair<double, double>> cr = {
        {0, 0},
        {0, s},
        {s, s},
        {s, 0},
    };

    set<pair<double, double>> pts(cr.begin(), cr.end());

    for (const auto& c : cr) {
        auto [rx, ry] = r(c.first, c.second, x1, y1, x2, y2);
        pts.insert({rx, ry});
    }

    for (const auto& p : pts) {
        cout << fixed << setprecision(2) << p.first << " " << p.second << endl;
    }

    return 0;
}

struct P {
    double a, b;
    P(double a = 0, double b = 0) : a(a), b(b) {}
};

P r(const P &p, double t) {
    return P(p.a * cos(t) - p.b * sin(t),
             p.a * sin(t) + p.b * cos(t));
}

pair<double, double> g(const vector<P> &q, double t) {
    double x1 = 1e9, x2 = -1e9, y1 = 1e9, y2 = -1e9;
    for (const auto &p : q) {
        P s = r(p, t);
        x1 = min(x1, s.a);
        x2 = max(x2, s.a);
        y1 = min(y1, s.b);
        y2 = max(y2, s.b);
    }
    return {x2 - x1, y2 - y1};
}

int main() {
    int n;
    cin >> n;
    vector<P> q(n);

    for (int i = 0; i < n; ++i) {
        cin >> q[i].a >> q[i].b;
    }

    double m = 1e9, w = 0, h = 0;

    for (int i = 0; i < 360; ++i) {
        double t = i * M_PI / 180.0;
        auto [cw, ch] = g(q, t);
        double a = cw * ch;
        if (a < m) {
            m = a;
            w = cw;
            h = ch;
        }
    }

    if (w > h) {
        swap(w, h);
    }

    cout << fixed << setprecision(0) << round(w) << " "
         << fixed << setprecision(0) << round(h);

    return 0;
}

struct P {
    double a, b;
    P(double a = 0, double b = 0) : a(a), b(b) {}
};

P r(const P &p, double t) {
    return P(p.a * cos(t) - p.b * sin(t),
             p.a * sin(t) + p.b * cos(t));
}

pair<double, double> g(const vector<P> &q, double t) {
    double x1 = 1e9, x2 = -1e9, y1 = 1e9, y2 = -1e9;
    for (const auto &p : q) {
        P s = r(p, t);
        x1 = min(x1, s.a);
        x2 = max(x2, s.a);
        y1 = min(y1, s.b);
        y2 = max(y2, s.b);
    }
    return {x2 - x1, y2 - y1};
}

int main() {
    int n;
    cin >> n;
    vector<P> q(n);

    for (int i = 0; i < n; ++i) {
        cin >> q[i].a >> q[i].b;
    }

    double m = 1e9, w = 0, h = 0;

    for (int i = 0; i < 360; ++i) {
        double t = i * M_PI / 180.0;
        auto [cw, ch] = g(q, t);
        double a = cw * ch;
        if (a < m) {
            m = a;
            w = cw;
            h = ch;
        }
    }

    if (w > h) {
        swap(w, h);
    }

    cout << fixed << setprecision(0) << round(w) << " "
         << fixed << setprecision(0) << round(h);

    return 0;
}