time limit per test: 0.25 sec.
memory limit per test: 65536 KB

input: standard
output: standard

Welcome to invincible black-white kings division, recruit! Here we will make true warriors out of you. You - best of the best, you - our new generation, we made you in our's own image, upgraded some functions. But not everyone of you can be a king... Army needs black-white knights, black-white bishops, black-white rooks and even black-white pawns. Who asks a question about black-white queens? You can completelly forget about it. It is an army, not a humanitarian faculty, son. Radiance in our blood! Forward, to training grounds!
Training grounds is an N x M chessboard, every cell of which can be empty, contain some colorless chess pieces (distance-controlled dummies), or ancient black-white king sculptures (they occupy cell as usual chess piece but can not move or attack you). You started at specified cell of the board, but before starting you must choose your chess piece. It can be any chess piece except a queen. You can make your moves according to chess rules. If after the turn you are under attack of some colorless chess piece, you lose (the training is over) and your score points is decreased by some penalty value. If you want you can leave training grounds in the beginning of any turn (not very patriotic) and do not lose any score points.
Colorless chess pieces do not make turns. After capturing colorless chess piece of some type your score is increased by a capturing bonus for that chess piece type. The number of your turns is not limited. Initially your score is 0.
You task is to achieve maximal possible score (you can lose, it is not important, all that is important - your score points after training).

The first line of input contains two integers N and M (1<=N, M<=300). The second line contains seven integers: capturing bonus points for pawn, rook, knight, bishop, queen, and king respectively, and the penalty value for losing. All these numbers are non-negative and not exceed 10000.
Next N lines contain M characters each. Legend is the following: "." - empty cell, "#" - ancient black-white king sculpture, "P" - pawn, "R" - rook, "K" - knight, "B" - bishop, "Q" - queen, "M" - king, "@" - your starting point (guaranteed that it exists and exactly one). It is considered (it is important for pawns only) that colorless chess pieces are oriented in direction of decreasing line numbers, and you are oriented in the opposite direction. Notice that the third line of input is the first line of the chessboard.
For simplicity if you choose a pawn you can not change your chess piece type when moving to the last line and can not make move from the second line to the fourth.

Output the maximal score you can achieve.

Input

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

Test #2
4 5
1 1 1 1 5 1 3
..@..
.K.K.
.Q...
.....