时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
大在与三体人战斗的过程中，不慎掉进了其布置的迷宫陷阱当中，他想要尽快从逃离这里。
迷宫由墙和路组成，大Z需要 开始出发走到
，每走一步的时间是
，其中墙不能通过。
大发现在迷宫的路上长有神奇的花朵，吃了这种花朵可以让时间倒流
，每个花朵只能吃一次，且花朵状态不会跟随时间倒流。
现在大 想让你计算他从
走到
所花费的时间。
输入描述:
第一行两个整数
表示迷宫的范围
随后行每行一个字符串表示对迷宫的描述
'.' 表示路
'#' 表示墙
'*' 表示花朵
保证第一行第一个字符为 '.'
输出描述:
一个数字 表示大
从
到
的最短时间，如果不能到达，输出