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

题目背景

大事不好了，大事不好了，强弟因为保护鸽鸽的蛋被黑坤党给抓了，于是强哥去黑坤党老巢黑坤市决定营救他

题目描述

黑坤市的地图可以看做 $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

提示

100%的数据满足 $5 \leq N,M \leq 25，1 \leq T \leq 1000$