시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB3222100.000%

문제

현정이는 직사각형 보드위에서 진행되는 전략 게임을 하고 있다. 보드는 단위 정사각형으로 나누어져 있으며, 일부 칸은 적이 차지하고 있다. 이제, 현정이의 턴이고 최대한 많은 적을 제거하려고 한다.

적이 차지하지 않고 있는 일부 칸에는 현정이의 레이저 타워가 있다. 각각의 레이저 타워는 위, 아래, 오른쪽, 왼쪽 중 한 방향을 바라보고 있다. 타워는 매우 높기 때문에, 바라보고 있는 방향에 있는 모든 칸을 공격할 수 있다.

각각의 타워에 대해서 레이저를 발사할지 말아야 할지를 결정해야 한다. 그 다음에는 어떤 칸으로 발사를 할지 결정해야 한다. 그 공격하기로 결정한 타워가 모두 동시에 결정하며, 공격 당한 칸에 있는 적은 모두 제거된다.

  • 레이저 타워는 서로 다른 레이저 타워를 공격할 수 없게 놓여져 있다.
  • 레이저를 발사할 때, 레이저가 서로 교차하면 안되며, 끝 점도 교차하면 안 된다. 즉, 각각의 을 공격할 수 잇는 칸은 최대 1개이다.

보드판의 상태가 주어졌을 때, 제거할 수 있는 적의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드판의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50)

둘째 줄부터 N개의 줄에는 보드판의 상태가 주어지며, 다음과 같은 의미를 가진다.

  • '.': 빈 칸
  • '1' ~ '9': 그 칸에 존재하는 적의 수
  • 'A', 'V', '<', '>': 레이저 타워가 가르키고 있는 방향 (북, 남, 서, 동)

출력

첫째 줄에 제거할 수 있는 적의 최대 수를 출력한다.

예제 입력 1

3 2
.9
>3
.A

예제 출력 1

9

예제 입력 2

4 5
..V..
>.54.
.>3.6
9..A.

예제 출력 2

12

예제 입력 3

3 4
.9V.
>..7
.A1.

예제 출력 3

10