#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
#include <cassert>
#include <random>

struct Coordinate {
	int x, y;
	std::vector<Coordinate> neighbors() const {
		return std::vector<Coordinate>{ Coordinate{x + 1, y}, Coordinate{x - 1, y}, Coordinate{x, y + 1}, Coordinate{x, y - 1} };
	}
};
std::vector<std::vector<int>> min_step(const Coordinate start, const std::vector<std::string>& state) {
	auto comparator = [](const std::pair<Coordinate, int>& a, const std::pair<Coordinate, int>& b) {return a.second > b.second; };
	std::priority_queue<std::pair<Coordinate, int>, std::vector<std::pair<Coordinate, int>>, decltype(comparator)> queue(comparator);
	std::vector<std::vector<int>> result(state.size(), std::vector<int>(state.front().size(), INT_MAX));
	queue.emplace(start, 0);
	result[start.y][start.x] = 0;
	while (!queue.empty()) {
		const auto top = queue.top(); queue.pop();
		if (result[top.first.y][top.first.x] == top.second) {
			for (const auto next : top.first.neighbors()) if (0 <= next.y && next.y < result.size() && 0 <= next.x && next.x < result[next.y].size()) {
				if (state[next.y][next.x] != '#' && result[next.y][next.x] > top.second + 1) {
					result[next.y][next.x] = top.second + 1;
					queue.emplace(next, top.second + 1);
				}
			}
		}
	}
	return result;
}
int bit_count(int x) {
	int res = 0;
	while (x > 0) {
		res += x % 2;
		x >>= 1;
	}
	return res;
}
int main() {
	int height, width, k; std::cin >> height >> width >> k;
	std::vector<std::string> state(height); for (auto& line : state) std::cin >> line;
	std::vector<Coordinate> apples; 
	Coordinate e, s;
	for (auto i = 0; i < height; ++i) for (auto j = 0; j < width; ++j) {
		if (state[i][j] == 'e') {
			e = Coordinate{ j, i };
		}
		else if (state[i][j] == 's') {
			s = Coordinate{ j, i };
		}
		else if (state[i][j] == 'a') {
			apples.push_back(Coordinate{ j, i });
		}
	}
	const auto from_start = min_step(e, state);
	const auto to_goal = min_step(s, state);
	apples.erase(std::remove_if(apples.begin(), apples.end(), [&from_start, &to_goal](const Coordinate& c) {return from_start[c.y][c.x] == INT_MAX || to_goal[c.y][c.x] == INT_MAX; }), apples.end());
	std::vector<std::vector<std::vector<int>>> min_steps; std::transform(apples.begin(), apples.end(), std::back_inserter(min_steps), [&state](const Coordinate from) {return min_step(from, state); });
	std::vector<std::vector<int>> min_distance(1 << apples.size(), std::vector<int>(apples.size(), INT_MAX));
	for (auto i = 0; i < apples.size(); ++i) {
		min_distance[1 << i][i] = from_start[apples[i].y][apples[i].x];
	}
	int min = INT_MAX;
	for (auto i = 0; i < min_distance.size(); ++i) {
		if (bit_count(i) >= k) {
			int m = INT_MAX;
			for (auto j = 0; j < apples.size(); ++j) if (min_distance[i][j] != INT_MAX) m = std::min(m, min_distance[i][j] + to_goal[apples[j].y][apples[j].x]);
			min = std::min(min, m);
			continue;
		}
		for (auto j = 0; j < apples.size(); ++j) if (min_distance[i][j] != INT_MAX) {
			for (auto k = 0; k < apples.size(); ++k) if ((i & (1 << k)) == 0 && min_steps[j][apples[k].y][apples[k].x] != INT_MAX) {
				if (min_distance[i | (1 << k)][k] > min_distance[i][j] + min_steps[j][apples[k].y][apples[k].x]) {
					min_distance[i | (1 << k)][k] = min_distance[i][j] + min_steps[j][apples[k].y][apples[k].x];
				}
			}
		}
	}
	std::cout << (min == INT_MAX ? -1 : min) << std::endl;
}


Measured memory_bytes: 213600