Laser Towers

Interview

Time limit2sMemory limit512 MB

Summary

On a grid with directional laser towers and enemy counts, choose which towers fire and at which cell so lasers never intersect, maximizing enemies destroyed.

Level: Hard8 of 10
Topics: Greedy, Brute force, Implementation, Matrix
Solved: No attempts yet

Problem

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.

Input

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

Output

Print the largest number of enemies that can be removed.

Examples3

Example 1
Input
```
3 2
.9
>3
.A
```
Expected output
```
9
```
Example 2
Input
```
4 5
..V..
>.54.
.>3.6
9..A.
```
Expected output
```
12
```
Example 3
Input
```
3 4
.9V.
>..7
.A1.
```
Expected output
```
10
```