U330826 伤心火星人

火星人在离开地球时遇到了许多陨石，很不巧小火星人好久不开飞船了，在被一块陨石撞击后，小火星人把姐姐的线索弄丢了！ 作为一个：  请帮助火星人，之后火星人会带你遨游太空

小火星人在一个长度为 $ n $ 的陨石阵里。 火星人身手敏捷，它可以原地造出一个长度为 $ k $ 的虫洞，而且无视任何地形，从中穿过也不需要时间。但火星人现在很着急，**虫洞能力只可以用一次** - ‘%’ 代表地球，起点。 - ‘#’代表陨石，不能走。 - ‘.’ 代表太空，可以走。 - ‘@’代表姐姐的线索。 - ‘*’代表火星，终点。 要先找到线索再回火星，不然火星人会很伤心，~~把你丢在太空中~~。

1. 第一行输入正整数 $ n $ 和 $ k $ 。表示陨石阵的长度和虫洞的长度。 1. 接下来输入 $ n $ 行 $ n $ 列的陨石阵

仅一行，输出火星人找到线索回到火星的最短时间。 （每走一步为一个火星时间） ~~火星人想快点回家吃饭~~

- $ 1 \le n \le 10^{3} $ - $ 1 \le k \le 10^{2} $ - 虫洞可以直接跳过这块区域，无论直走还是转弯 - 虫洞最大长度为 $ k $ ，当然了小于 $ k $ 也行