Let's play a game! The game field is a rectangular grid with $$$n$$$ rows and $$$m$$$ columns $$$n$$$ and $$$m$$$ are both odd. There are domino tiles on this grid; each domino covers two horizontally or vertically adjacent cells. At the beginning of the game, every cell, except for one, is covered by precisely one domino tile, and one cell is empty.
During each more, you can slide any domino tile in the direction parallel to its orientation, provided that the cell in that direction is empty. You can perform this move as many times as you like, and you can stop at any time.
Every cell on the game field has a positive or negative cost. When you slide a domino tile, some cell previously covered by that tile becomes empty. If this is the first time this cell becomes empty during the game, you add its cost to the overall score.
Figure out a sequence of moves that maximizes the total score, that is, the sum of the costs of all cells that were empty at least once during the game.
The first line contains two integers $$$n$$$ and $$$m$$$ — the number of rows and columns of the grid ($$$1 \le n, m \le 499$$$; $$$n$$$ and $$$m$$$ are odd). The following $$$n$$$ lines contain $$$m$$$ characters each — the initial arrangement of dominoes. The empty cell is denoted by ., a horizontal tile — by a pair of characters < (the left cell) and > (the right cell), and a vertical tile — by a pair of character ^ (the top cell) and v (the bottom cell). It's guaranteed that the arrangement is correct and there's one empty cell.
The following $$$n$$$ lines contain $$$m$$$ integers each, describing the costs of cells. The cost of each cell is an integer from $$$-1000$$$ to $$$1000$$$ inclusive. The initially empty cell has cost $$$0$$$.
Print a single integer — the maximum possible final score.
| Subtask | Points | Constraints |
| 1 | 10 | $$$n = 1$$$, $$$m \le 3$$$ |
| 2 | 24 | $$$n = 1$$$, $$$m \le 499$$$ |
| 3 | 14 | $$$n, m \le 7$$$ |
| 4 | 23 | $$$n, m \le 499$$$, all costs are non-negative |
| 5 | 29 | No additional constraints |
1 5 <>.<> 5 2 0 9 -2
5
3 3 <>^ ^.v v<> 1 1 1 1 0 1 1 1 1
0
