Problem: G, a college student living in a certain sky city, has a hornworm, Imotaro. He disciplined Imotaro to eat all the food in order with the shortest number of steps. You, his friend, decided to write a program because he asked me to find out if Imotaro was really disciplined.



Input


H W N
area


Input is given in H + 1 lines. The first line contains three integers H, W, N (2 ≤ H ≤ 10, 2 ≤ W ≤ 10, 1 ≤ N ≤ 9). H is the height of the area, W is the width, and N is the number of foods (at this time, 6 + N ≤ H × W always holds).

In each line from the 2nd line to H + 1st line, ´S´, ´1´, 2´,… ´9´, ´a´, ´b´, ´c´, ´d´, ´e´, A W character string consisting of ´ # ´ and ´.´ is written, and each represents the state of each section of the area. In addition, ´S´, ´a´, ´b´, ´c´, ´d´, ´e´ represent the initial state of the hornworm. There is no food or obstacles so that it is covered with the hornworm in the initial state. In addition, the initial position of the hornworm and the position of the food are guaranteed to be entered correctly.

Output

Output the minimum number of steps when the hornworm eats food in order, or -1 if that is not possible.

Examples

Input

5 8 3
#.......
#.####2#
#.#.3..#
#.######
.1Sabcde


Output

14


Input

5 8 3
.......
.####2#
.#.3..#
.######
.1Sabcde


Output

14


Input

2 6 2
.1.baS
.2.cde


Output

7


Input

2 6 2
.1#baS
.2.cde


Output

-1

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define SIZE 5

enum DIR{
	North,
	West,
	East,
	South,
};

struct LOC{
	void set(int arg_row,int arg_col){
		row = arg_row;
		col = arg_col;
	}
	int row,col;
};

struct Info{
	Info(int arg_row,int arg_col,int arg_last_num,int arg_sum_cost,DIR arg_dir[SIZE],LOC arg_loc[SIZE+1]){

		row = arg_row;
		col = arg_col;
		last_num = arg_last_num;
		sum_cost = arg_sum_cost;

		for(int i = 0; i < SIZE; i++){
			dir[i] = arg_dir[i];
		}

		for(int i = 0; i < SIZE+1; i++){

			loc[i] = arg_loc[i];
		}
	}

	int row,col,last_num,sum_cost;
	DIR dir[SIZE];
	LOC loc[SIZE+1];
};

int H,W;
int N;
int POW[6],diff_row[4] = {-1,0,0,1},diff_col[4] = {0,-1,1,0};
int min_cost[10][10][10][1024];
LOC start;
DIR dir_array[4] = {North,West,East,South};
char base_map[10][11],sequence[SIZE+1] = {'S','a','b','c','d','e'};


bool rangeCheck(int row,int col){

	return row >= 0 && row <= H-1 && col >= 0 && col <= W-1;
}

//体の位置関係をコード化
int makeCode(DIR dir[SIZE]){

	int ret = 0;

	for(int i = 0; i < SIZE; i++){

		ret += dir[i]*POW[i];
	}

	return ret;
}

//初期状態での、体の位置および位置関係を調べる
void calc_First(int base_row,int base_col,LOC loc[SIZE+1],DIR dir[SIZE]){

	loc[0].set(base_row,base_col);

	for(int i = 1; i < 6; i++){
		for(int a = 0; a < 4; a++){

			int adj_row = loc[i-1].row+diff_row[a];
			int adj_col = loc[i-1].col+diff_col[a];

			if(rangeCheck(adj_row,adj_col) == false)continue;

			if(base_map[adj_row][adj_col] == sequence[i]){
				loc[i].set(adj_row,adj_col);
				dir[i-1] = dir_array[a];
				break;
			}
		}
	}
}

//同じマスに2つ以上の部分が乗っていないか調べる
bool cross_Check(LOC loc[SIZE+1]){

	for(int i = 0; i < 5; i++){
		for(int k = i+1; k < 6; k++){
			if(loc[i].row == loc[k].row && loc[i].col == loc[k].col){

				return false;
			}
		}
	}

	return true;
}

int main(){

	POW[0] = 1;
	for(int i = 1; i < 6; i++){

		POW[i] = POW[i-1]*4;
	}

	scanf("%d %d %d",&H,&W,&N);

	LOC first_loc[SIZE+1];
	DIR first_dir[SIZE];

	//先に全部読み込む
	for(int row = 0; row < H; row++){

		scanf("%s",base_map[row]);
	}

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){

			if(base_map[row][col] == 'S'){

				start.set(row,col);
				calc_First(row,col,first_loc,first_dir);
			}
		}
	}

	//dp[row][col][最後の数字][体の位置関係] = 最小コスト
	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){
			for(int num = 0; num <= N; num++){
				for(int state = 0; state < POW[5]; state++){
					min_cost[row][col][num][state] = BIG_NUM;
				}
			}
		}
	}

	queue<Info> Q;

	min_cost[start.row][start.col][0][makeCode(first_dir)] = 0;
	Q.push(Info(start.row,start.col,0,0,first_dir,first_loc));

	int next_last_num,next_cost;
	DIR next_dir[SIZE];
	LOC next_loc[SIZE+1];

	while(!Q.empty()){

		if(Q.front().sum_cost > min_cost[Q.front().row][Q.front().col][Q.front().last_num][makeCode(Q.front().dir)]){

			Q.pop();

		}else if(Q.front().last_num == N){

			printf("%d\n",Q.front().sum_cost);
			return 0;

		}else{

			for(int i = 0; i < 4; i++){

				int adj_row = Q.front().row+diff_row[i];
				int adj_col = Q.front().col+diff_col[i];

				if(rangeCheck(adj_row,adj_col) == false || base_map[adj_row][adj_col] == '#')continue;

				if(base_map[adj_row][adj_col] >= '1' && base_map[adj_row][adj_col] <= '9' &&
						base_map[adj_row][adj_col]-'0' == Q.front().last_num+1){

					next_last_num = base_map[adj_row][adj_col]-'0';

				}else{

					next_last_num = Q.front().last_num;
				}

				next_cost = Q.front().sum_cost+1;

				//次の体の位置を計算
				for(int a = 5; a >= 1; a--){
					//前のパーツがあった場所へ動く
					next_loc[a].row = Q.front().loc[a-1].row;
					next_loc[a].col = Q.front().loc[a-1].col;
				}
				next_loc[0].set(adj_row,adj_col);

				if(!cross_Check(next_loc))continue;

				//各パーツの位置関係を計算
				for(int a = 1; a < 6; a++){
					for(int b = 0; b < 4; b++){

						if(next_loc[a-1].row+diff_row[b] == next_loc[a].row &&
								next_loc[a-1].col+diff_col[b] == next_loc[a].col){

							next_dir[a-1] = dir_array[b];
							break;
						}
					}
				}

				int next_code = makeCode(next_dir);

				if(min_cost[adj_row][adj_col][next_last_num][next_code] > next_cost){

					min_cost[adj_row][adj_col][next_last_num][next_code] = next_cost;
					Q.push(Info(adj_row,adj_col,next_last_num,next_cost,next_dir,next_loc));
				}
			}

			Q.pop();
		}
	}

	printf("-1\n");

	return 0;
}