//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 より
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

//

fn run() {
    input! {
        h: usize,
        w: usize,
        k: usize,
        s: [chars; h],
    }
    let mut start = 0;
    let mut end = 0;
    let mut point = vec![];
    for i in 0..h {
        for j in 0..w {
            if s[i][j] == 's' || s[i][j] == 'e' || s[i][j] == 'a' {
                if s[i][j] == 's' {
                    start = point.len();
                }
                if s[i][j] == 'e' {
                    end = point.len();
                }
                point.push((i, j));
            }
        }
    }
    let len = point.len();
    if end != len - 1 {
        point.swap(end, len - 1);
        if start == len - 1 {
            start = end;
        }
        end = len - 1;
    }
    if start != len - 2 {
        point.swap(start, len - 2);
        start = len - 2;
    }
    let mut d = vec![vec![0; point.len()]; point.len()];
    let inf = 2000u16 * 22 + 1;
    for i in 0..point.len() {
        let (a, b) = point[i];
        let mut dp = vec![vec![inf; w]; h];
        dp[a][b] = 0;
        let mut q = std::collections::VecDeque::new();
        q.push_back((a, b));
        while let Some((a, b)) = q.pop_front() {
            for &(x, y) in [(a - 1, b), (a + 1, b), (a, b - 1), (a, b + 1)].iter() {
                if x < h && y < w && s[x][y] != '#' && dp[x][y] > dp[a][b] + 1 {
                    dp[x][y] = dp[a][b] + 1;
                    q.push_back((x, y));
                }
            }
        }
        for j in 0..point.len() {
            let p = point[j];
            d[i][j] = dp[p.0][p.1];
        }
    }
    let m = point.len() - 2;
    let mut dp = vec![vec![inf; 1 << m]; m];
    let mut q = std::collections::VecDeque::new();
    for i in 0..m {
        dp[i][(1 << m) - 1] = d[start][i];
        q.push_back((i, (1 << m) - 1));
    }
    for bit in (0..(1 << m)).rev() {
        for now in 0..m {
            if (bit >> now) & 1 == 0 {
                continue;
            }
            let b = bit ^ (1 << now);
            for j in 0..m {
                let cost = dp[now][bit].saturating_add(d[now][j]);
                if (b >> j) & 1 == 1 && dp[j][b] > cost {
                    dp[j][b] = cost;
                }
            }
        }
    }
    let mut ans = inf;
    for now in 0..m {
        for bit in 0..(1 << m) {
            if m + 1 - (bit as usize).count_ones() as usize >= k {
                let v = dp[now][bit].saturating_add(d[now][end]);
                ans = std::cmp::min(ans, v);
            }
        }
    }
    if ans < inf {
        println!("{}", ans);
    } else {
        println!("-1");
    }
}

fn main() {
    run();
}



Measured memory_bytes: 51436