463. Walking around Berhattan
Time limit per test: 0.25
second(s)
Memory limit: 65536
kilobytes
input: standard
output: standard
As you probably know, Berhattan is a district of Berland's largest city and it consists of equal square blocks. There are
n block lines in the eastwest direction and
m block lines in the southnorth direction. The map shows Berhattan as a rectangle with
n rows and
m columns, so there are
nx
m blocks in total.
There are
n+1 streets running parallel in the eastwest direction (horizontally), and there are
m+1 avenues running parallel in the southnorth direction (vertically). Streets and avenues split the district into blocks and separate Berhattan from other districts of Berland. Each block in Berhattan is characterized by its beauty
b_{ij}.
A pedestrian can walk only along streets and avenues. When the pedestrian walks along any of four sides of a block, we say he passes the block. Every time the pedestrian passes a block his satisfaction is increased by
b_{ij}. If the pedestrian has already passed the block one or more times his satisfaction is increased only by
b_{ij}/2 rounded down when he passes the block again.
You are given the map of Berhattan with the information about the blocks' beauty and the pedestrian's path along the streets and avenues. The path is given as a string containing letters '
L
', '
R
' and '
M
', where '
L
' means a 90 degree left turn, '
R
' means a 90 degree right turn, and '
M
' means walking one block forward by a street or avenue. Facing the east, the pedestrian starts his path in the northwest corner of Berhattan having zero satisfaction level. His path can cross itself and go along the same streets or avenues several times. Pedestrian's satisfaction is increased every time he moves according to the rules described above.
Your task is to calculate the total satisfaction the pedestrian will get after finishing his route.
Picture of the sample test Input
The first line of input contains two integers
n and
m (1 ≤
n,
m ≤ 100), where
n is a number of block lines in Berhattan running in the eastwest direction, and
m is a number of block lines in Berhattan running in the southnorth direction. The following
n lines contain
m digits each. The
jth digit of the
ith line represents
b_{ij} (0 ≤
b_{ij} ≤ 9) — the beauty of the corresponding block. The last line of input contains a path in the format specified above. The path consists of 1 up to 500 characters, inclusively. It is guaranteed that the given path doesn't go outside Berhattan.
Output
Print a single integer to the output — the total pedestrian's satisfaction.
Example(s)
sample input

sample output

3 3
123
456
789
MRMMLM

22
