슈퍼 배관공

슈퍼 배관공(SP)이 장애물 코스를 헤쳐 나가며 상품을 모으고, 오른쪽 아래에 있는 공주(TP)를 구출하는 비디오 게임을 위한 프로그램을 작성한다.

장애물 코스는 $m \times n$ 격자다. SP는 왼쪽 아래 칸에서 출발해 오른쪽 아래 칸에 있는 공주에게 도달해야 한다. 일부 칸에는 SP가 통과할 수 없는 장애물이 있고, 다른 칸에는 $1.00부터 $9.00까지의 값을 가진 금화가 놓여 있다.

이 게임은 전통적인 횡스크롤 게임이므로 SP는 오른쪽, 위, 아래로만, 한 번에 한 칸씩, 장애물이 없는 인접한 칸으로만 이동할 수 있다. 이미 지나온 칸에는 다시 들어갈 수 없다. 즉, 위로 이동한 뒤에는 다음에 오른쪽으로 이동하기 전까지 아래로 내려갈 수 없고, 아래로 이동한 뒤에는 다음에 오른쪽으로 이동하기 전까지 위로 올라갈 수 없다. SP는 지나는 모든 칸의 금화를 획득한다. 왼쪽 아래 칸에서 오른쪽 아래 칸까지 가는 경로에서 SP가 모을 수 있는 금화 값의 합의 최댓값을 구하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $m$과 $n$이 주어진다 ($2 \le m, n \le 100$). 이어서 $n$개의 문자로 이루어진 $m$개의 줄로 격자가 주어진다.

• *는 장애물을,
• 숫자 1~9는 그 값을 가진 금화를,
• .은 빈 칸을 나타낸다.

SP가 공주에게 도달하는 것은 항상 가능하다. 마지막 테스트 케이스 뒤에는 0 0으로 이루어진 줄이 오며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 한 줄에, 왼쪽 아래 칸에서 오른쪽 아래 칸까지 가는 올바른 경로에서 SP가 모을 수 있는 금화 값의 합의 최댓값을 출력한다. 모든 금화는 정수 달러 값이므로 답은 정수이며, 달러 기호나 소수 부분 없이 정수로 출력한다.