题目背景

旅行者又又又没原石抽奶奶了（是谁不用说），ta现在要去寻找宝箱获得原石。 （图片暂时没有）

题目描述

已知一张地图（以二维矩阵的形式表示）以及旅行者和宝箱的位置。地图上的每个位置都可以走到，只不过有些位置上有丘丘人，需要先打败丘丘人才能到这些位置。旅行者有一定数量的技能，每一个单位的技能可以击杀丘丘人。假设旅行者可以往上下左右四个方向移动，每移动一个距离需要花费1个单位时间，击杀丘丘人不需要时间。如果旅行者技能消耗完了，则只可以走到没有丘丘人的位置，不可以再移动到有丘丘人的位置。丘丘人不会移动。请问，旅行者要获得宝箱最少需要花费多少时间？

输入格式

输入的第一行包含三个整数：$M，N，S$。代表M行N列的地图和旅行者初始的技能数量$S$。$0 < M,N < 200，0 ≤ S < 10$

后面是$M$行$N$列的地图，其中$@$代表旅行者，$o$代表宝箱。$*$代表通路，$\#$代表丘丘人。

输出格式

输出包含一个整数$T$，代表旅行者找到宝箱最少需要花费的时间。如果旅行者无法找到宝箱，则输出$-1$。

样例

3 3 2
@*#
***
#*o

4

2 4 1
@#*o
****

3

数据范围

$0 < M,N < 200，0 ≤ S < 10$

$1s, 1024KiB$.