Problem E: PIPI的意大利炮

Problem E: PIPI的意大利炮

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 100  Solved: 63
[Submit] [Status] [Web Board] [Creator:]

Description

由于李云龙的二营长临时有事,现在由PIPI来管理意大利炮啦。为了提高炮兵营的作战能力,PIPI决定进行特训。意大利炮可以看成由炮管,车轮,炮弹三部分组成。PIPI分别把炮管,车轮,炮弹放在三个不同的地方,每一部分的重量不同,所以运输的速度也不相同。
现在PIPI要你从地图的某一位置出发,用最快的速度把炮管,车轮,炮弹收集好带到PIPI的面前。
零件只要拿起,就不能放下,所以说不存在在a点拿起,b点放下再去取别的零件一说。默认1秒走一个单位距离,并且只能向上下左右四个方向走,假设现在拿着炮管,那么每走一单位距离则需要(t1 + 1)秒,如果再拿上车轮,那么现在每走一步则需要(t1 + t2+1)秒的时间,以此类推。点可以重复经过,路过有零件的点时,可以选择拿或者不拿。

Input

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

Output

输出一个整数并换行,代表和尚完成任务所需要的最短时间。

Sample Input

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

Sample Output

34