#include <cstdio>
#include <utility>
#include <queue>
#include <vector>

const int SIZE=1000;
const int APPLE_NUM=20;

using namespace std;

typedef pair<int,int> coordinate;

// 迷宮自体
int H,W,K;
char maze[SIZE][SIZE+1];

// 各ラウンドでアクセスしたか
char maze_visited[SIZE][SIZE][APPLE_NUM+2];

// 林檎と人の位置
int total_a_num,S_index,E_index;
vector<coordinate> key_points;
coordinate S,E;

// 各林檎の間の距離、人を含む
int dist_vec[22][22];



void init_dist(){
    for (int i=0;i<22;i++)
        for (int j=0;j<22;j++)
            dist_vec[i][j]=-1;
}

char get_maze_item(const coordinate& pos){
    return maze[pos.second][pos.first];
}

bool in_maze(const coordinate& pos){
    return pos.first>=0&&pos.first<W&&pos.second>=0&&pos.second<H;
}

bool pos_visited(const coordinate& pos,int i){

    return maze_visited[pos.second][pos.first][i];
}

void explore_pos(const coordinate& pos,int i,queue<coordinate>& Q,queue<int>& dist_Q,int cur_dist){
    if (in_maze(pos) && !pos_visited(pos, i) && get_maze_item(pos)!= '#')
        Q.push(pos),
        maze_visited[pos.second][pos.first][i] = 1, 
        dist_Q.push(cur_dist + 1);
    ;
    ;
}

int find_index(const coordinate& pos){
    for (int i=0;i<key_points.size();i++)
        if (key_points[i]==pos) return i;
}

void BFS(int vert){
    coordinate ini;

    ini=key_points[vert];
    
    queue<coordinate> Q;
    queue<int> dist_Q;
    explore_pos(ini, vert, Q, dist_Q, -1);
    // dist_Q.push(0);
    
    // printf("vert=%d,pos=(%d,%d)\n", vert,ini.second,ini.first);

    while (!Q.empty()){
        //
        const coordinate cur=Q.front();
        const int cur_dist=dist_Q.front();
        Q.pop();
        dist_Q.pop();

        // printf("(%d,%d),dist=%d\n",cur.second,cur.first,cur_dist);

        //todo
        char maze_item=get_maze_item(cur);
        if (maze_item=='a'||maze_item=='e'||maze_item=='s'){
            int index=find_index(cur);
            dist_vec[vert][index]=cur_dist;
            dist_vec[index][vert] = cur_dist;
        }
        

        coordinate left(cur.first-1,cur.second)
        ,right(cur.first+1,cur.second)
        ,up(cur.first,cur.second-1)
        ,down(cur.first,cur.second+1);

        // 左のポジションを探索
        explore_pos(left,vert,Q,dist_Q,cur_dist);
        

        // 左のポジションを探索
        explore_pos(right, vert, Q, dist_Q, cur_dist);

        // 左のポジションを探索
        explore_pos(up, vert, Q,dist_Q, cur_dist);

        // 左のポジションを探索
        explore_pos(down, vert, Q, dist_Q, cur_dist);
    }

}

bool is_possible(){
    if (dist_vec[S_index][E_index]==-1)
        return false;

    int count=0;
    for (int i=0;i<total_a_num;i++)
        if (dist_vec[S_index][i]!=-1) count++;

    return count>=K;
}


int dp[20][1<<20];

int bit_count(int state){
    int c=0;
    for(int l=0;l<total_a_num;l++)
        if (state&(1<<l)) c++;

    return c;
}

int solve(){
    int POW[25]={1};
    int ans=0;
    for (int i=1;i<25;i++) POW[i]=POW[i-1]*2;

    for (int i=0;i<total_a_num;i++) dp[i][POW[i]]=dist_vec[S_index][i];

    for (int state=1;state<POW[total_a_num];state++){
        for (int apple=0;apple<total_a_num;apple++){
            if (dp[apple][state]==0)
                continue;

            if (bit_count(state)==K){
                if (ans==0)
                    ans=dp[apple][state]+dist_vec[apple][E_index];
                else
                    ans = min(dp[apple][state] + dist_vec[apple][E_index],ans);
            }

            for (int loop = 0; loop < total_a_num; loop++)
            {
                if (state & (1 << loop))
                {

                    //Do nothing
                }
                else
                {
                    if (dist_vec[apple][loop]==-1)
                        continue;
                    int next_state = state | POW[loop];
                    int next_dist = dp[apple][state] + dist_vec[apple][loop];

                    if (dp[loop][next_state]==0)
                        dp[loop][next_state] = next_dist;
                    else
                        dp[loop][next_state] = min(dp[loop][next_state], next_dist);
                }
            }
        }
    }

    return ans;
}

int main(){
    //迷宮を初期化
    scanf("%d%d%d\n",&H,&W,&K);
    for (int i=0;i<H;i++) {
        for (int j=0;j<W;j++){
            maze[i][j]=getchar();

            // 座標をX,Yに並ぶ
            coordinate cur_pos = coordinate(j, i);
            if (maze[i][j] == 's')
                S = cur_pos ;

            if (maze[i][j] == 'e')
                E = cur_pos;

            if (maze[i][j] == 'a')
                key_points.push_back(cur_pos);
        }
        getchar();
    }

    init_dist();

    total_a_num=key_points.size();
    S_index=total_a_num;
    E_index=total_a_num+1;
    key_points.push_back(S);
    key_points.push_back(E);

    // for (auto a:key_points)
    //     printf("(%d,%d)\n",a.first,a.second);

    BFS(S_index);

    // for (int i=0;i<total_a_num+2;i++)
    //     printf("%d ",dist_vec[S_index][i]);
    // putchar('\n');

    // for (int i = 0; i < total_a_num + 2; i++)
    //     printf("%d ", dist_vec[i][S_index]);
    // putchar('\n');

    if (!is_possible()){
        puts("-1");
        return 0;
    }

    for (int i=0;i<total_a_num+2;i++)
        if (i!=S_index&&dist_vec[S_index][i]!=-1)
            BFS(i);

    // for (int i=0;i<total_a_num+2;i++){
    //     for(int j=0;j<total_a_num+2;j++)
    //         printf("%d ",dist_vec[i][j]);

    //     putchar('\n');
    // }

    printf("%d\n",solve());

    // 初期化異常無し
    // for (int i = 0; i < H; i++)
    // {
    //     for (int j = 0; j < W; j++)
    //         putchar(maze[i][j]);
    //     putchar('\n');
    // }

    return 0;
}


Measured memory_bytes: 90836