Laser Towers

Hyeonjeong is playing a strategy game on a rectangular board. The board is divided into unit square cells, and enemies occupy some of the cells. It is Hyeonjeong's turn, and she wants to remove as many enemies as possible.

Some of the cells that hold no enemy hold one of Hyeonjeong's laser towers. Each tower faces north, south, west, or east. A tower is very tall, so it can attack every cell that lies in the direction it faces.

For each tower Hyeonjeong decides whether to fire, and every tower that fires picks one cell in the direction it faces as its target. All firing towers fire at the same time, and every enemy in a target cell is removed. Enemies in a cell that a laser only passes over stay.

The placement and the shots obey these rules.

• No tower can attack another tower. That is, no other tower lies in the direction a tower faces.
• A fired laser travels in a straight line from the cell that holds the tower to its target cell. Two lasers share no cell, and a target cell may not lie on the line of another laser. At most one laser attacks or passes over any single cell.

Given the board, write a program that finds the largest number of enemies that can be removed.

The first line contains the height $N$ and the width $M$ of the board. ($1 \le N, M \le 50$)

Each of the next $N$ lines contains $M$ characters describing one row of the board. The characters mean the following.

• .: an empty cell
• 1 to 9: the number of enemies in that cell
• A, V, <, >: a laser tower facing north, south, west, or east

Print the largest number of enemies that can be removed.