题目

小杨最近放暑假了，她想去参加一个迷宫挑战，规则是这样的： 迷宫是一个边长为n的正方形，玩家需要从迷宫的左上角走到迷宫的右下角，其中"."表示可以走的地方，"#"表示不能通行的障碍物，玩家可以在1秒钟之内移动到相邻的地方（上、下、左、右）。但不同于其他的迷宫，在这次挑战中，会有一些工作人员扮演的鬼怪（用"G"表示），玩家遇到鬼怪（即走到鬼怪所在的位置）后在接下来的k秒内会以2倍的速度逃离（即一秒钟可以走两个格子），逃离期间再次遇到鬼怪不会重置时间。节目组保证迷宫一定能走出去 小杨听完规则后感觉十分的烧脑，由于她沉迷于内卷，无法独自算出需要多久才能走出迷宫，于是她来问聪明的你

输入

第一行是一个整数n（2 <= n <= 10），表示迷宫的边长 第二行是一个整数k（0 <= k <= n × n），表示小杨在遇到鬼怪后会有k秒加速效果 接下来是一个n * n的字符矩阵，包含且仅包含字符"."，"#"，"G"。

输出

一个整数，表示走出这个这个迷宫所需的最短时间

样例

5
0
.....
####.
.....
.####
.....

16

6
3
......
#G.#..
##.#..
...#..
.##...
......

9

样例2说明

第1秒：(1,1)->(1,2) 第2秒：(1,2)->(2,2) 第3秒：由于遇到了鬼怪，所以在接下来的3秒内（第3至5秒）可以以2倍速度行走。(2,2)->(2,3)->(1,3) 第4秒：(1,3)->(1,4)->(1,5) 第5秒：(1,5)->(1,6)->(2,6) 第6秒：(2,6)->(3,6) 第7秒：(3,6)->(4,6) 第8秒：(4,6)->(5,6) 第9秒：(5,6)->(6,6)