광석수집 2 timer 1s memory 128MB

오늘은 권수쌤이 크기 N \times M인 광산에서 광물을 캐는 부업을 하는 날이다.
광산은 세 가지 종류의 칸으로 구성되어 있다:

• 평범한 돌로 이루어진 칸 (이동 가능)

• 단단한 바위로 이루어진 칸 (이동 불가능)

• 황금이 묻힌 칸 (이동 가능하며, 지나가면 황금을 1개 얻는다)

  

최근 운동을 쉬어 근력이 약해진 권수쌤은 단단한 바위로 이루어진 칸을 통과할 수 없다.
또한 체력도 예전 같지 않아서 항상 오른쪽 또는 아래쪽 방향으로만 이동하기로 했다.

광산의 가장 왼쪽 위 칸 (1, 1)에서 시작하여, 가장 오른쪽 아래 칸 (N, M)에 도착할 때까지 얻을 수 있는 황금의 최대 개수를 구하시오.

단, 출발지 (1,1) 혹은 도착지 (N,M)가 단단한 바위로 막혀 있거나, 어떠한 경로로도 도착할 수 없는 경우는 황금을 얻을 수 없으므로 정답은 0이 된다.