题目描述

训练场是一张 $N\times M$ 的棋盘。棋盘中可能包含：

• .：空格；
• #：雕像。它占据一个格子，会阻挡移动和远程棋子的攻击，但不会移动、不会攻击，也不能被吃掉；
• P：兵；
• R：车；
• K：马；
• B：象；
• Q：后；
• M：王；
• @：你的初始位置。

除雕像外，上述棋子都是静止不动的无色棋子。

在训练开始前，你必须选择自己扮演的棋子类型，可以选择：

• 兵；
• 车；
• 马；
• 象；
• 王。

你不能选择后。

之后你按照国际象棋中该棋子的规则移动。若移动到一个无色棋子所在的格子，则吃掉该棋子，并获得该棋子种类对应的奖励分数，被吃掉的棋子会从棋盘上消失。

每完成一次移动后，如果你当前所在格子受到任意一个仍然存在的无色棋子攻击，那么训练立即结束，并从总分中扣除给定的惩罚值。

在任意一次移动开始前，你都可以主动离开训练场，此时不会受到惩罚。因此也允许在一开始直接离开，获得 $0$ 分。

所有无色棋子始终不移动。

兵的方向

输入中的无色兵面向行号减小的方向，因此它们攻击上一行的两个斜对角格子。

如果你选择兵，则你的方向与无色兵相反，即朝行号增加的方向移动。

为简化规则：

• 你的兵到达最后一行后不会升变；
• 兵不能执行从第二行一次走到第四行的首次两格移动。

其他移动、吃子以及车、象、后的射线阻挡规则均按普通国际象棋规则处理。

你的初始得分为 $0$，移动次数不限。

求最终能够获得的最大分数。

输入格式

第一行包含两个整数 $N,M$：

$1\le N,M\le300$。

第二行包含七个整数：

p r k b q m penalty

依次表示吃掉兵、车、马、象、后、王所获得的奖励，以及训练失败时扣除的惩罚。

这些数均满足：

$0\le p,r,k,b,q,m,penalty\le10000$。

接下来 $N$ 行，每行包含 $M$ 个字符，描述棋盘。

保证字符 @ 恰好出现一次。

输出格式

输出一行一个整数，表示能够获得的最大分数。

样例 1

样例输入

4 5
1 1 1 1 1 1 10
..@..
.K.K.
.Q...
.....

样例输出

1

样例 2

样例输入

4 5
1 1 1 1 5 1 3
..@..
.K.K.
.Q...
.....

样例输出

2