Problem: Apple adventure

square1001 and E869120 got lost in the grid world of $ H $ rows and $ W $ rows!

Said the god of this world.

"When you collect $ K $ apples and they meet, you'll be back in the original world."

Upon hearing this word, square1001 decided to collect more than $ K $ of apples and head to the square where E869120 is.




Here, each cell in the grid is represented as follows.

's': square1001 This is the square where you are.

'e': E869120 This is the square where you are.

'a': A square with one apple on it. You can get an apple the first time you visit this trout. There are no more than 20 squares on this grid.

'#': It's a wall. You cannot visit this square.

'.': A square with nothing. You can visit this square.




square1001 You try to achieve your goal by repeatedly moving from the square you are in to the squares that are adjacent to each other up, down, left, and right. However, you cannot get out of the grid.

square1001 Find the minimum number of moves you need to achieve your goal.

However, it is assumed that E869120 will not move. Also, square1001 shall be capable of carrying $ K $ or more of apples.

If the goal cannot be achieved, output "-1".

input

Input is given from standard input in the following format.

Let $ A_ {i, j} $ be the characters in the $ i $ square from the top of the grid and the $ j $ square from the left.


$ H $ $ W $ $ K $
$ A_ {1,1} A_ {1,2} A_ {1,3} \ cdots A_ {1, W} $
$ A_ {2,1} A_ {2,2} A_ {2,3} \ cdots A_ {2, W} $
$ A_ {3,1} A_ {3,2} A_ {3,3} \ cdots A_ {3, W} $
$ \ ldots $
$ A_ {H, 1} A_ {H, 2} A_ {H, 3} \ cdots A_ {H, W} $


output

square1001 Find the minimum number of moves you need to reach your goal. However, if this is not possible, output "-1".

However, insert a line break at the end.

Constraint

* $ 1 \ leq H \ leq 1000 $
* $ 1 \ leq W \ leq 1000 $
* $ 1 \ leq K \ leq 20 $
* $ H, W, K $ are integers.
* $ A_ {i, j} $ is one of's','e','a','#','.'.
* The grid contains only one's' and one'e'.
* The number of'a'in the grid is greater than or equal to $ K $ and less than or equal to $ 20 $.



Input example 1


5 5 2
s .. # a
. # ...
a # e. #
... # a
. # ...


Output example 1


14


Input example 2


7 7 3
.......
.s ... a.
a ## ... a
.. ### ..
.a # e # .a
. ### ..
a .. # .. a


Output example 2


-1


If the purpose cannot be achieved, output "-1".

Input example 3


12 12 10
. ##### ......
.## ..... # ...
.... a.a # a .. #
. # .. # a ......
..... a # s ..
..a ###. ##. #
.e #. #. #. # A ..
.. # a # ..... #.
.. ## a ......
.a ... a.a .. #.
a .... # a.aa ..
... a. # ... # a.


Output example 3


30






Example

Input

5 5 2
s..#a
.#...
a#e.#
...#a
.#...


Output

14

Solution (in CPP):

Solution:
#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;
}