{"raw_statement":[{"iden":"statement","content":"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 east-west direction and m block lines in the south-north direction. The map shows Berhattan as a rectangle with n rows and m columns, so there are n × m blocks in total.\n\nThere are n + 1 streets running parallel in the east-west direction (horizontally), and there are m + 1 avenues running parallel in the south-north 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_ bij. \n\nA 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 bij. If the pedestrian has already passed the block one or more times his satisfaction is increased only by bij / 2 rounded down when he passes the block again.\n\nYou 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 north-west 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.\n\nYour task is to calculate the total satisfaction the pedestrian will get after finishing his route.\n\nThe 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 east-west direction, and m is a number of block lines in Berhattan running in the south-north direction. The following n lines contain m digits each. The j-th digit of the i-th line represents bij (0 ≤ bij ≤ 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.\n\nPrint a single integer to the output — the total pedestrian's satisfaction.\n\n"},{"iden":"input","content":"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 east-west direction, and m is a number of block lines in Berhattan running in the south-north direction. The following n lines contain m digits each. The j-th digit of the i-th line represents bij (0 ≤ bij ≤ 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."},{"iden":"output","content":"Print a single integer to the output — the total pedestrian's satisfaction."},{"iden":"examples","content":"Input3 3123456789MRMMLMOutput22"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of east-west and south-north block lines, respectively.  \nLet $ B = (b_{i,j}) \\in \\{0,1,\\dots,9\\}^{n \\times m} $ be the beauty matrix, where $ b_{i,j} $ is the beauty of the block at row $ i $, column $ j $.  \nLet $ P \\in \\{L, R, M\\}^* $ be the path string of length $ \\ell $, representing the pedestrian’s movements.  \n\nThe pedestrian starts at position $ (0, 0) $ (north-west corner), facing east.  \nEach block $ (i,j) $ is bounded by:  \n- Horizontal streets: $ i $ (north) and $ i+1 $ (south)  \n- Vertical avenues: $ j $ (west) and $ j+1 $ (east)  \n\nLet $ c \\in \\{0,1,\\dots,n\\} \\times \\{0,1,\\dots,m\\} $ be the current position (street, avenue).  \nLet $ d \\in \\{0,1,2,3\\} $ be the current direction: 0=east, 1=south, 2=west, 3=north.  \nLet $ v_{i,j} \\in \\mathbb{N} $ be the number of times block $ (i,j) $ has been passed (each side traversal counts as one pass).  \n\n**Constraints**  \n1. $ 1 \\leq n, m \\leq 100 $  \n2. $ 0 \\leq b_{i,j} \\leq 9 $ for all $ i \\in \\{0,\\dots,n-1\\}, j \\in \\{0,\\dots,m-1\\} $  \n3. $ 1 \\leq |P| \\leq 500 $  \n4. Path stays within bounds: $ 0 \\leq c_{\\text{street}} \\leq n $, $ 0 \\leq c_{\\text{avenue}} \\leq m $  \n\n**Objective**  \nSimulate the path, updating position and direction:  \n- 'M': move one unit in direction $ d $, crossing one block side.  \n  - If moving east: from $ (i,j) $ to $ (i,j+1) $ → passes block $ (i,j) $  \n  - If moving south: from $ (i,j) $ to $ (i+1,j) $ → passes block $ (i,j) $  \n  - If moving west: from $ (i,j) $ to $ (i,j-1) $ → passes block $ (i,j-1) $  \n  - If moving north: from $ (i,j) $ to $ (i-1,j) $ → passes block $ (i-1,j) $  \n- 'L': turn left: $ d \\leftarrow (d + 3) \\mod 4 $  \n- 'R': turn right: $ d \\leftarrow (d + 1) \\mod 4 $  \n\nFor each block pass:  \n- If $ v_{i,j} = 0 $: add $ b_{i,j} $ to satisfaction  \n- Else: add $ \\left\\lfloor \\frac{b_{i,j}}{2} \\right\\rfloor $ to satisfaction  \n- Increment $ v_{i,j} \\leftarrow v_{i,j} + 1 $  \n\nCompute total satisfaction after processing all steps in $ P $.  \n\nOutput: total satisfaction.","simple_statement":"A pedestrian walks on streets and avenues in a grid of n rows and m columns of blocks. Each block has a beauty value from 0 to 9. Every time the pedestrian walks past a side of a block, he gains satisfaction: full beauty value the first time, half (rounded down) for each later pass. He starts at the top-left corner, facing east. His path is given as a string of 'L' (left turn), 'R' (right turn), and 'M' (move forward one block). Calculate his total satisfaction after following the entire path.","has_page_source":false}