Orange走迷宫III

题目描述

没想到吧，这个沟槽的b题目还有III...xD

Orange现在身处在一个 $n \times m$ 大小的迷宫之中，Orange出生在 $(1, 1)$ 处，迷宫的终点位于 $(n,m)$，Orange每次可以向上下左右的四个相邻的格子上移动（前提是不越界且目标格子不能是墙），这样做的不消耗任何代价。同时，Orange由于之前玩泡泡堂，他手里还留有若干个钻头炸弹，他可以用钻头炸弹，摧毁一整列的墙，摧毁第 $i$ 列墙的代价为 $w_i$。Orange想知道他从起点走到终点需要的最少代价是多少？

输入格式

第一行为两个整数 $n,m$，表示地图大小。 接下来 $n$ 行为一张由字符串构成的 $n \times m$ 大小的地图，其中.表示路径，#表示墙。 最后一行为 $m$ 个整数 $w_i$，表示摧毁第 $i$ 列墙需要的代价。

数据范围

$1 \leq n,m \leq 100$ $1 \leq w_i \leq 10^5$

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

4 4
.##.
.#.#
.###
..#.
5 3 9 4

样例输出 #1

7