기념품 구매 계획 (Gifts)

오스트레일리아로 여행을 온 JOI 군은 여러 곳에서 관광을 즐긴 끝에, 드디어 귀국하는 날을 맞았습니다. 지금 JOI 군은 귀국 비행기가 출발하는 국제공항이 있는 마을에 있습니다. 이 마을은 동서남북으로 구획이 나뉘어 있으며, 각 구획은 길, 기념품 가게, 주택, 국제공항 중 하나입니다.

JOI 군은 가장 북서쪽 구획에서 출발하여 가장 남동쪽 구획에 있는 국제공항을 향해 갑니다.

JOI 군은 지금 있는 구획에서 인접한 구획으로 이동할 수 있지만, 주택이 있는 구획에는 들어갈 수 없습니다. 또한 비행기 시간에 맞추기 위해 원칙적으로는 지금 있는 구획의 동쪽 또는 남쪽 구획으로만 이동합니다. 다만 시간에 다소 여유가 있으므로, 지금 있는 구획의 북쪽 또는 서쪽 구획으로는 통틀어 최대 $K$ 번까지 이동할 수 있습니다.

JOI 군은 기념품 가게가 있는 구획에 들어가면 일본에 있는 친구들을 위해 기념품을 삽니다. JOI 군은 기념품 가게를 미리 꼼꼼히 조사해 두었기 때문에, 어느 가게에 가면 기념품을 몇 개 살 수 있는지 알고 있습니다. JOI 군이 살 수 있는 기념품 개수의 최댓값을 구하는 프로그램을 작성하세요.

단, 기념품을 사는 시간은 무시할 수 있다고 하며, 같은 기념품 가게를 두 번 이상 방문한 경우에는 처음 방문했을 때만 기념품을 삽니다.

입력은 $1 + H$ 줄로 이루어집니다.

첫째 줄에는 세 정수 $H$, $W$, $K$ ($2 \le H \le 50$, $2 \le W \le 50$, $1 \le K \le 3$)가 공백으로 구분되어 주어집니다.

이어지는 $H$ 줄에는 각각 $W$ 개의 문자로 이루어진 문자열이 주어지며, 구획의 정보를 나타냅니다. 북쪽에서 $i$ 번째, 서쪽에서 $j$ 번째 구획을 $(i, j)$ 로 나타냅니다 ($1 \le i \le H$, $1 \le j \le W$). $i$ 번째 줄의 $j$ 번째 문자는 다음과 같습니다.

• 구획 $(i, j)$ 가 길 또는 국제공항이면 .
• 주택이면 #
• 기념품 가게이면 1, 2, $\dots$, 9 중 하나이며, 그 숫자는 해당 가게에서 살 수 있는 기념품 개수를 나타냅니다.

주어지는 입력에서, JOI 군이 처음 있는 가장 북서쪽 구획은 길임이 보장됩니다. 또한 JOI 군이 국제공항에 도달할 수 있음이 보장됩니다.

JOI 군이 살 수 있는 기념품 개수의 최댓값을 나타내는 정수를 한 줄에 출력하세요.

첫 번째 예제에서 JOI 군은 남쪽으로 $3$ 번 이동하여 구획 $(4, 1)$ 의 기념품 가게에서 물건을 산 뒤, 다시 남쪽으로 $1$ 번, 동쪽으로 $3$ 번 이동하고, 거기서 북쪽으로 $2$ 번 이동하여 구획 $(3, 4)$ 의 기념품 가게에서 물건을 삽니다. 마지막으로 남쪽으로 $2$ 번 이동하여 국제공항에 도달하면, 합계 $11$ 개의 기념품을 살 수 있습니다.

이처럼 JOI 군은 국제공항이 있는 구획을 지나쳤다가 다시 돌아올 수도 있으며, 최종적으로 국제공항 구획에서 여정을 마치면 됩니다.