题目背景

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

题目描述

黑虎市的地图可以看做 $n \times m$ 的网格，虎哥在起点 $s$，虎弟在终点 $m$。营救路途并不平坦：

• . 表示顺畅路段，耗时 1 单位
• # 表示拥堵路段，耗时 2 单位
• o 表示维修路段，无法通过

虎哥必须在 $T$ 单位时间内到达终点（耗时需严格小于 $T$），否则小虎子就会在虎弟面前跳《虎你太美》。

输入格式

1. 第一行：整数 $T$（可用时间）
2. 第二行：整数 $n$（网格列数）
3. 第三行：整数 $m$（网格行数）
4. 接下来 $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$