古希腊之争

题目描述

伯罗奔尼撒战争是以雅典为首的提洛同盟与以斯巴达为首的伯罗奔尼撒联盟之间的一场战争。这场战争从前431年一直持续到前404年，使得绝大多数周边城邦必须加入其中一方的阵营。战争第一阶段（BC431-BC421），雅典在伯里克利的领导之下，凭借强大的海军，采取陆地上防御在海上进攻的策略。而斯巴达在阿基达摩斯二世的领导之下，率领它令人畏惧的战士进行陆地强攻。两个强邦侧重点不同的军事力量导致了战争第一阶段的僵持局面。

话说，有一天阿基达摩斯二世决定率兵进攻雅典的一个居民点阿提卡，当他们满怀斗志地奔向阿提卡的时候，殊不知他们正走向伯利克里所设下的迷宫陷阱之中。当他们发现时，已为时已晚。

为了早日返回斯巴达，阿基达摩斯二世立即让所有的斯巴达勇士去寻找迷宫的出口 $E$。现在他们被困在迷宫的 $S$ 点，迷宫中. 表示空地，可以通过，# 表示墙，不能通过。每次只能向上下左右四个方向移动，每个勇士每移动一个单位距离需要耗费一个单位时间，所有斯巴达勇士的移动速度相同。

假设迷宫中每个点可以容纳的人数没有限制，请你计算一下他们所有人都找到迷宫的出口时，最短需要的时间之和是多少。

输入格式

第一行输入三个整数 $n,m,c$，分别代表迷宫的长度（列数）、宽度（行数），以及被困迷宫的斯巴达勇士数。

接下来 $m$ 行，每行有 $n$ 个字符，用来表示迷宫地图。

输出格式

输出一个整数，表示所有勇士找到出口时消耗的最短时间之和。若存在勇士无法找到出口，请输出 -1。

样例

输入

5 5 100
#####
#S..#
#...#
#...E
#####

输出

500

说明/提示

数据范围

对于 $100\%$ 的数据，满足： $2 \le m \le n \le 500$，$100 \le c \le 10000$

限制

• 时间限制：$1$ 秒
• 内存限制：$128$ MB