1640: [STT2024Nov+] 地地的闭眼禅
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：2
题目描述
### 题目背景
$$ “闭上眼睛，便是另一视域。” $$
### 题目描述
地地喜欢睡觉，睡觉时会闭眼，这便是 **闭眼禅**。
通过禅意，地地可以感知到平时忽略的 **异域** 事物。
这天，地地在睡醒后发现，自己竟然被困在了森林里，这直接把地地给吓睡着了。
经过冷静后，地地发现，森林的地形构成一个 $n \times m$ 的地图，其中`.`表示空地，`#`表示障碍。地地目前处在位置 $S$，森林的出口在位置 $T$，保证 $S,T$ 所在位置均为空地。
地地每次可以花费 $1$ 点气力从一个空地移动到一个相邻的空地。
若地地当前在现实，则地地可以花费 $f$ 点气力入睡，开启闭眼禅，感知异域的道路。异域的地形也构成一个 $n \times m$ 的地图。若地地当前处在异域，则地地可以花费 $g$ 点气力醒来，回到现实。
若地地在试图入睡或醒来之后，处于一个障碍内，则认为地地此时不能切换领域。
那么，地地最少花费多少气力，可走出森林？如果地地无论如何都不能走出森林，输出`Be Lost`。
$$ “闭上眼睛，便是另一视域。” $$
### 题目描述
地地喜欢睡觉，睡觉时会闭眼，这便是 **闭眼禅**。
通过禅意，地地可以感知到平时忽略的 **异域** 事物。
这天，地地在睡醒后发现，自己竟然被困在了森林里，这直接把地地给吓睡着了。
经过冷静后，地地发现，森林的地形构成一个 $n \times m$ 的地图，其中`.`表示空地，`#`表示障碍。地地目前处在位置 $S$，森林的出口在位置 $T$，保证 $S,T$ 所在位置均为空地。
地地每次可以花费 $1$ 点气力从一个空地移动到一个相邻的空地。
若地地当前在现实，则地地可以花费 $f$ 点气力入睡，开启闭眼禅，感知异域的道路。异域的地形也构成一个 $n \times m$ 的地图。若地地当前处在异域，则地地可以花费 $g$ 点气力醒来，回到现实。
若地地在试图入睡或醒来之后，处于一个障碍内，则认为地地此时不能切换领域。
那么，地地最少花费多少气力，可走出森林？如果地地无论如何都不能走出森林，输出`Be Lost`。
输入
第一行，四个正整数 $N,M,f,g$。
接下来 $N$ 行，每行 $M$ 个字符 $a_i$，表示现实的地图。
再接下来 $N$ 行，每行 $M$ 个字符 $a_i$，表示异域的地图。
接下来 $N$ 行，每行 $M$ 个字符 $a_i$，表示现实的地图。
再接下来 $N$ 行，每行 $M$ 个字符 $a_i$，表示异域的地图。
输出
一个整数，表示地地至少需要消耗多少气力，才能走出森林。
样例输入 复制
5 7 3 2
#S#####
###.##T
###.###
#######
#.#.#.#
#.#####
#.###..
#.###.#
#.....#
#######样例输出 复制
15提示
### 样例 #2
#### 样例输入 #2
```
3 3 998 244
S#.
#.#
.#.
..#
.#.
#.T
```
#### 样例输出 #2
```
Be Lost
```
### 提示
**【数据范围】**
对于 $20\%$ 的数据，$1 \leq n,m \leq 500$。
对于 $100\%$ 的数据，$1 \leq n,m \leq 10^3$，$1 \leq f,g \leq 10^5$，保证 $S,T$ 出现且仅出现一次，但不保证 $S,T$ 在同一领域。