求助黑坤市的地图可以看做 � ∗ � n∗m 的网格，强哥在 � s 点,强弟在 � m 点。找强弟的路途并不是一帆风顺的，. 表示顺畅的路段， 需要花费一点时间；而 # 表示拥堵的地点，需要花费两点时间；o 表示正在维修，无法通过。

强哥救援强弟的时间只有 � T 点时间。如果没有在 � T 点时间内到达 � m 点找到强弟，小黑子就会在强弟面前跳鸡你太美(太难了，强弟)。（请注意是 � T 点时间内，即所花时间小于 � T） 第一行输入 � T，表示强哥拥有的时间。 第二行输入 � N，第三行输入 � M 接下来 � M 行，每行输入 � N 个字符，表示 黑坤市*的地图。

输出格式 如果强哥能在 � T 点时间救助到强弟，请输出所用最短时间。 如果不能，请输出 The End。 样例： 11 10 8 ......s... .......... #ooooooo.o #......... #......... #......... #.....m... #......... 输出10