りんごだいぼうけん

square1001君とE869120君は縦 $H$ 行、横 $W$ 列のグリッドの世界に迷い込んでしまいました!

この世界の神は言いました。

「リンゴを $K$ 個集めて二人が出会ったとき、さすれば元の世界に帰れるであろう。」

この言葉を聞いたsquare1001君は、リンゴを $K$ 個以上集めてE869120君がいるマスへ向かうことにしました。

ここで、グリッドの各マスは次のように表されます。

's'：square1001君がいるマスです。

'e'：E869120君がいるマスです。

'a'：リンゴが1つ落ちているマスです。このマスを初めて訪れたときにリンゴを1つ得ることができます。このグリッド上にこのマスは20個以下しかありません。

'#'：壁です。このマスに訪れることはできません。

'.'：何もないマスです。このマスに訪れることができます。

square1001君は自分がいるマスから上下左右に隣り合うマスへの移動を繰り返すことで、目的を達成しようとします。ただし、グリッドから外に出ることはできません。

square1001君が目的を達成するために必要な移動回数の最小値を求めてください。

ただし、E869120君が動くことはないものとします。また、square1001君はリンゴを $K$ 個以上持ち運ぶ能力があるものとします。

また、目標が達成できないときは「-1」を出力してください。

入力

入力は以下の形式で標準入力から与えられる。

グリッドの上から $i$ マス目、左から $j$ マス目の文字を $A_{i, j}$ とする。

$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}$

出力

square1001君が目的を達成するまでに必要な移動回数の最小値を求めてください。ただし、不可能な場合は「-1」を出力してください。

ただし、最後には改行を入れること。

制約

• $1 \leq H \leq 1000$
• $1 \leq W \leq 1000$
• $1 \leq K \leq 20$
• $H, W, K$ は整数である。
• $A_{i, j}$ は 's'、'e'、'a'、'#'、'.'のいずれかである。
• グリッドに 's'、'e'はそれぞれただ 1 つのみ含まれる。
• グリッドに含まれる 'a' の数は $K$ 個以上 $20$ 個以下である。

入力例1

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

出力例1

14

入力例2

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

出力例2

-1

目的が達成不可能な場合は「-1」を出力してください。

入力例3

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

出力例3

30