花花的地图

题号：NC275050
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

A市地图是一个 $n \times m$ 的网格图，字符'#'表示障碍，'.' 表示空地。花花住在左上角 $(1,1)$ ，花花的朋友萌萌住在右下角 $(n,m)$ 。花花要去萌萌家玩。
花花如果走到空地则不需要任何代价，但是如果要走到障碍点则他需要先摧毁该障碍。每次可以走到相邻的四个方向之一，即从 $(x,y)$ 可以走到 $(x+1,y)$ ， $(x-1,y)$ ， $(x,y+1)$ ， $(x,y-1)$ 。
花花可以花费 $C_i$ 的代价将第 $i$ 列的所有障碍都消灭。
请帮花花计算她去萌萌家最少需要多少代价。

输入描述:

第一行输入两个正整数，，为网格图的大小。
接下来 行，每行 个字符，描述迷宫的地图。字符仅由'.','#'，保证起点一定是空地。
接下来一行个正整数，为消灭第列的障碍的代价

输出描述:

输出一个整数，为从花花家到萌萌家的最小代价。

示例1

输入

复制

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

输出

复制

说明

消除第2列和第4列的障碍，总代价为7