5613 - 提高：迷宫问题
Time Limit : 1 秒
Memory Limit : 128 MB
简单描述：在一个n行m列的表格里，你在左上角1,1位置，你准备到右下角，即可n行m列的位置，在这个表格里，‘.’表示无任何代价就可以到，‘#’，表示障碍，需要一定成本拆除后才能到，你只能上下左右四个方向走； 每列的拆除代价为ci,即你可以花费ci的代价把i列的障碍拆除
Input
第一行输入两个正整数n，m，为网格图的大小。 接下来n 行，每行m 个字符，描述迷宫的地图。字符仅由'.','#'，保证起点一定是空地。 接下来一行m个正整数Ci ，为消灭第i列的障碍的代价。
1≤n,m≤100
1≤Ci≤10^5
Output
输出一个整数，为到达目的地的最小代价。
Examples
Input
4 4 .##. .#.# .### ..#. 5 3 9 4
Output
7
Hint
消除第2列和第4列的障碍，总代价为7