题目描述

飞机位于地图第一行的 v 格。# 是障碍，. 可通行。每次可左移、右移或下移一格，左右移动各耗1能量，下移不耗能量。每一行内消耗的能量不能超过 $K$。求到达最后一行的最少总能量，无法到达输出-1。

输入格式

第一行 $R,C,K$，接下来 $R$ 行长度为 $C$ 的地图。每行两端是连续障碍，中间是连续的非空通行段。第一行有且仅有一架飞机。

输出格式

输出最少能量或-1。

样例

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

3

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

-1

1 7 47
#...v.#

0

数据范围

$1\le R\le50$，$3\le C\le50$，$0\le K\le47$。