#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>

using namespace std;

struct pos {
    int x, y;
};
int h, w;

bool inRange(pos p) {
    return 0 <= p.x && p.x < h && 0 <= p.y && p.y < w;
}

const int INF = 514810114;
const vector<pos> moves{{1,  0},
                        {-1, 0},
                        {0,  1},
                        {0,  -1}};
vector<vector<bool>> can;

vector<vector<int>> bfs(pos start) {
    vector<vector<int>> ret(h, vector<int>(w, INF));
    queue<pos> que;
    que.push(start), que.push({-1, -1});

    int depth = 0;
    while (true) {
        pos now = que.front();
        que.pop();
        if (now.x < 0) {
            if (que.empty())break;
            que.push({-1, -1}), depth++;
        } else {
            ret[now.x][now.y] = depth;
            for (auto move:moves) {
                pos next = {now.x + move.x, now.y + move.y};
                if (inRange(next) && ret[next.x][next.y] == INF && can[next.x][next.y]) {
                    ret[next.x][next.y] = -1;
                    que.push(next);
                }
            }
        }
    }

    return ret;
}

int main() {
    int k;
    cin >> h >> w >> k;

    pos start, end;
    vector<pos> apples;
    can = vector<vector<bool>>(h, vector<bool>(w));
    for (int i = 0; i < h; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < w; j++) {
            switch (s[j]) {
                case 's': {
                    start = {i, j};
                    break;
                }
                case 'e': {
                    end = {i, j};
                    break;
                }
                case 'a': {
                    apples.push_back({i, j});
                    break;
                }
                default: {
                    break;
                }
            }
            if (s[j] != '#')can[i][j] = true;
        }
    }

    int count = apples.size();
    vector<vector<int>> fromStart = bfs(start);
    vector<vector<int>> toEnd = bfs(end);
    vector<vector<vector<int>>> applesdis(count);
    for (int i = 0; i < count; i++)applesdis[i] = bfs(apples[i]);

    vector<vector<int>> dp(1 << count, vector<int>(count, 1145141919));
    for (int i = 0; i < count; i++) {
        dp[1 << i][i] = fromStart[apples[i].x][apples[i].y];
    }

    int ret = INF;
    for (int i = 0; i < (1 << count); i++) {
        vector<bool> avail(count);
        int tmp = 0;
        for (int j = 0; j < count; j++) {
            if (i & (1 << j)) {
                avail[j] = true;
                tmp++;
            }
        }
        if (tmp < 1)continue;

        if (tmp >= k) {
            for (int last = 0; last < count; last++) {
                if (avail[last]) {
                    int uku = dp[i][last];
                    int tapu = toEnd[apples[last].x][apples[last].y];
                    ret = min(ret, uku + tapu);
                }
            }
        }

        for (int prev = 0; prev < count; prev++) {
            if (!avail[prev])continue;
            for (int now = 0; now < count; now++) {
                if (avail[now])continue;

                int nbit = i | (1 << now);
                int cost = applesdis[prev][apples[now].x][apples[now].y];
                dp[nbit][now] = min(dp[nbit][now], dp[i][prev] + cost);
            }
        }
    }

    cout << (ret < INF ? ret : -1) << endl;
    return 0;
}


Measured memory_bytes: 212744