题目描述

小 Z 来到了一个迷宫的入口，这个迷宫可以看作是 $n\times m$ 的网格图，入口是迷宫中的 s 点，终点是 m 点。

小 Z 在这个迷宫中可以向上、下、左、右四个方向移动，迷宫中的点有以下几类：

• s、m 分别表示入口和出口

• . 表示是顺畅的路，需要花费 $1$ 单位时间

• # 表示是拥堵的路，需要花费 $2$ 单位时间

• o 表示这个路正在维修，无法通过

问小 Z 能否在 $t$ 单位时间内到达迷宫的终点。

「注意」

$t$ 单位时间内的意思指的是，小 Z 花费的时间需要小于 $t$。

输入格式

第一行输入一个整数 $t$。

第二行输入两个整数 $n,m$ 分别表示迷宫的行数和列数。

接下来有 $n$ 行，每行 $m$ 个字符表示迷宫。

输出格式

如果小 Z 可以在 $t$ 时间内到达终点，输出所需的最短时间。

否则，输出 The End。

样例 #1

样例输入 #1

11
8 10
......s...
..........
#ooooooo.o
#.........
#.........
#.........
#.....m...
#.........

样例输出 #1

10

提示

$5\le n, m \le 25, 1 \le t \le 1000$。