该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

有一个由 $N×M$ 个方格组成的迷宫，每个方格写有一个字母 $A$ 或者 $B$。小蓝站在迷宫左上角的方格，目标是走到右下角的方格。他每一步可以移动到上下左右相邻的方格去。

由于特殊的原因，小蓝的路线必须先走 $K$ 个 $A$ 格子、再走 $K$ 个 $B$ 格子、再走 $K$ 个 $A$ 格子、再走 $K$ 个 $B$ 格子......如此反复交替。

请你计算小蓝最少需要走多少步，才能到达右下角方格? 注意路线经过的格子数不必一定是 $K$ 的倍数，即最后一段 $A$ 或 $B$ 的格子可以不满 $K$ 个。起点保证是 $A$ 格子。

例如 $K=3$ 时，以下 $3$ 种路线是合法的:

AAA
AAAB
AAABBBAAABBB

以下 $3$ 种路线不合法:

ABABAB
ABBBAAABBB
AAABBBBBBBAAA

输入格式

输入共 $2$ 行。

第一行包含三个整数 $N、M$ 和 $K$。

以下 $N$ 行，每行包含 $M$ 个字符 ($A$ 或 $B$)，代表格子类型。

输出格式

一个整数，代表最少步数。如果无法到达右下角，输出 -1。

样例

4 4 2 
AAAB 
ABAB 
BBAB 
BAAA

8

样例说明

每一步方向如下：下右下右上右下下；路线序列：AABBAABBA。

评测用例规模与约定

对于 $20\%$ 的数据，$1≤N,M≤4$。

对于另 $20\%$ 的数据，$K=1$。

对于 $100\%$ 的数据，$1≤N,M≤1000,1≤K≤10$。