기념품 구매 계획

문제

오스트레일리아에 여행을 온 JOI 군은 여러 장소에서 관광을 즐겼고, 마침내 귀국하는 날이 찾아왔다. 지금 JOI 군은 돌아가는 비행기가 출발하는 국제공항이 있는 마을에 있다. 이 마을은 동서남북으로 구획 정리되어 있으며, 각 구획에는 길, 기념품 가게, 주택, 국제공항이 있다. JOI 군은 가장 북서쪽 구획에서 출발하여 가장 남동쪽 구획의 국제공항을 목표로 한다.

JOI 군은 지금 있는 구획에서 인접한 구획으로 이동할 수 있지만, 주택이 있는 구획에는 들어갈 수 없다. 또한 비행기 시간에 맞추기 위해 지금 있는 구획의 동쪽 또는 남쪽 구획으로만 이동한다. 단, 시간에 어느 정도 여유가 있기 때문에 K 번까지는 지금 있는 구획의 북쪽 또는 서쪽 구획으로 이동할 수 있다.

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

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

입력

입력은 1 + H 줄로 이루어진다.

첫째 줄에는 세 정수 H, W, K (2 ≦ H ≦ 50, 2 ≦ W ≦ 50, 1 ≦ K ≦ 3) 이 공백으로 구분되어 주어진다.

이어지는 H 줄에는 각각 W 문자로 이루어진 문자열이 주어지며, 구획의 정보를 나타낸다. 북쪽에서 i 번째, 서쪽에서 j 번째 구획을 (i, j) 로 나타낸다 (1 ≦ i ≦ H, 1 ≦ j ≦ W). i 번째 줄의 j 번째 문자는, 구획 (i, j) 가 길 또는 국제공항인 경우에는 '.' 이고, 주택인 경우에는 '#' 이다. 기념품 가게인 경우에는 '1', '2', ..., '9' 중 하나이며, 그 기념품 가게에서 살 수 있는 기념품의 개수를 나타낸다.

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

출력

JOI 군이 구입할 수 있는 기념품의 개수의 최댓값을 나타내는 정수를 한 줄에 출력한다.

예제 입력 1

5 4 2
...#
.#.#
.#73
8##.
....

예제 출력 1

11

예제 1 에서 JOI 군은 남쪽으로 3 번 나아가 구획 (4, 1) 의 기념품 가게에서 쇼핑을 한 후, 다시 남쪽으로 1 번, 동쪽으로 3 번 나아가고, 거기서 북쪽으로 2 번 나아가는 것으로 구획 (3, 4) 의 기념품 가게에서 쇼핑을 한다. 마지막으로 남쪽으로 2 번 나아가 국제공항에 도달하면, 합계 11 개의 기념품을 살 수 있다.

예제 입력 2

4 4 3
.8#9
9.#.
.#9.
....

예제 출력 2

27