题目描述

自攻打过太原县城以后，李云龙这意大利炮就使用的越发的顺手了，指哪打哪也是绝不含糊，于是小野队长开始疯狂打击独立团炮兵营，为了锻炼士兵移动意大利炮的能力，李团长开始给炮兵营进行特训，众(wo)所(xia)周(bian)知(de)，意大利炮可由炮管，车轮，炮弹三部分组成，现在李团长在洋村设立阵地，分别把炮管，车轮，炮弹放在三个不同的地方，每一部分的重量不同，所以运输的速度也不相同。团长说：你谁有能耐最快把这意大利炮组装好然后运到我面前，老子就赏他半斤地瓜烧，和尚听了乐坏了，但是他不知道怎么才能使时间最快，你能帮帮他么？ 零件只要拿起，就不能放下，所以说不存在在 $a$ 点拿起，$b$ 点放下再去取别的零件一说。默认和尚 1 秒走一个单位距离，只能向上下左右四个方向走，并且带上一件零件，速度就会相应下降一点，假设和尚现在只拿着炮管（时间消耗为 $t_1$），那么他每走一单位距离则需要（$t_1 + 1$）秒，如果只拿着车轮（时间消耗为 $t_2$），那么他每走一单位距离则需要（$t_2 + 1$）秒，如果拿上炮管和车轮，那么他每走一步则需要（$t_1 + t_2+1$）秒的时间，以此类推。点可以重复经过，路过有零件的点时，可以选择拿或者不拿。

输入格式

第一行给定两个整数 $n, m$ 代表地图大小，$(1≤n, m ≤ 100)$； 接下来 $n$ 行每行有 $m$ 个由 ‘#’ 和 ‘.’ 组成的字符，‘#’ 代表墙，‘.’ 代表路，和尚功夫高，可以自己或者带着零件翻墙(不论墙多厚)，但是组装好意大利炮之后就必需得走路了。地图画好之后，接下来一行有 10 个整数 $sx,sy,x1, y1, x2, y2, x3, y3, ex, ey$(都小于 100)代表五个点，分别是起始点，炮管的位置，车轮的位置，炮弹的位置，李团长的位置(终点)， 五个点保证不同。 最后一行三个整数 $t_1, t_2, t_3$，(都大于等于 1，小于 100)，分别代表带着炮管，车轮，炮弹每走一单位距离需要的时间。题目保证数据合法。

输出格式

输出一个整数并换行，代表和尚完成任务所需要的最短时间。题目保证有解。

样例

输入#1

3 5
##.##
.#.#.
##.##
1 3 2 1 2 3 2 5 3 3 
1 5 4

输出#1

34

解释#1

对于第一组样例，我们发现只有在2号零件也就是车轮的位置组装完才能运回到李团长的位置，所以最优解为：起始点->1号零件 –> 3号零件-> 2号零件->李团长 路线为(1,3),(2,3),(2,2),(2,1),(2,2),(2,3),(2,4),(2,5),(2,4),(2,3),(3,3)。 答案为34。