题目描述

您正在玩一个游戏，给出一个地图，地图实际是一个 $R$ 行 $C$ 列的二维字符数组。'#' 表示障碍物,'.' 表示可通行格子，'v' 表示飞机。游戏中只有 $1$ 架飞机，而且在第 $1$ 行。

游戏有 $3$ 个键：向左键、向右键、下降键。其中向左键可以把飞机向左移动一个格子，向右键可以把飞机向右移动一个格子，下降键可以把飞机向下移动一个格子。每按一次向左键需 要消耗 $1$ 个能量，每按一次向右键需要消耗 $1$ 个能量，每按一次下降键需要消耗 $0$ 个能量。

有一个特殊规定：对于地图的任意一行，飞机在该行所消耗的能量都不能超过 $K$。

你的任务是控制飞机降落，顺利到达第 $R$ 行，不能碰到障碍物，而且消耗的总能量最少。

例如下图，$R=7$, $C=9$, $K=2$：

##..v..##
###.....#
#####...#
####...##
###..####
#.......#
#...#####

其中一种最优的方案是：

1. 在第一行按“向右键”、“下降键”
2. 在第二行按“下降键”
3. 在第三行按“下降键”
4. 在第四行按“向左键”、“下降键”
5. 在第五行按“向左键”、“下降键”
6. 在第六行按“下降键”
7. 顺利到达最后一行。

总共消耗 $3$ 个能量，已经是最优解了。

输入格式

第一行，$3$ 个整数：$R、C、K$。 $1 \le R \le 50$， $3 \le C \le 50$, $0 \le K \le 47$。

接下来是 $R$ 行 $C$ 列的二维地图。

对于地图的每一行来说，开头都是连续的若干个障碍物格子，结尾也是连续的若干个障碍物格子，中间是连续的可通行格子（看题干描述的例子）。第一行比较特殊，因为有驾飞机，所以有一个可通行格子被 'v' 替代了。

输出格式

一个整数，顺利完成任务所需要消耗的最少能量。如果不能完成任务，输出 -1。

样例

7 9 2
##..v..##
###.....#
#####...#
####...##
###..####
#.......#
#...#####

3

4 5 0
#.v.#
##..#
###.#
#...#

-1

1 7 47
#...v.#

0