有一个由 N × M 个方格组成的迷宫，每个方格写有一个字母 A 或者 B。小 蓝站在迷宫左上角的方格，目标是走到右下角的方格。他每一步可以移动到上 下左右相邻的方格去。
由于特殊的原因，小蓝的路线必须先走 K 个 A 格子、再走 K 个 B 格子、 再走 K 个 A 格子、再走 K 个 B 格子……如此反复交替。
请你计算小蓝最少需要走多少步，才能到达右下角方格？ 注意路线经过的格子数不必一定是 K 的倍数，即最后一段 A 或 B 的格子 可以不满 K 个。起点保证是 A 格子。
例如 K = 3 时，以下 3 种路线是合法的：
AA
AAAB
AAABBBAAABBB
以下 3 种路线不合法：
ABABAB
ABBBAAABBB
AAABBBBBBAAA
第一行包含三个整数 N、M 和 K。
以下 N 行，每行包含 M 个字符（A 或 B），代表格子类型。
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。