오스트레일리아로 여행 온 JOI 군은 여러 곳을 구경하고, 드디어 귀국하는 날이 되었다. 지금 JOI 군은 돌아가는 비행기가 뜨는 국제공항이 있는 마을에 있다. 이 마을은 동서남북으로 구획이 나뉘어 있고, 각 칸에는 길, 기념품 가게, 주택, 국제공항이 있다. JOI 군은 가장 북서쪽 칸에서 출발해 가장 남동쪽 칸의 국제공항으로 가려 한다. JOI 군은 지금 있는 칸에서 이웃한 칸으로 이동할 수 있지만, 주택이 있는 칸에는 들어갈 수 없다. 비행기 시간에 맞추려고 지금은 동쪽 또는 남쪽 칸으로만 이동한다. 다만 시간에 여유가 조금 있어서, \(K\)번까지는 북쪽 또는 서쪽 칸으로 이동할 수 있다. JOI 군은 기념품 가게가 있는 칸에 들어가면 일본의 친구들을 위해 기념품을 산다. 어느 가게에서 몇 개를 살 수 있는지는 미리 조사해 두었다. JOI 군이 살 수 있는 기념품 개수의 최댓값을 구하는 프로그램을 작성하라. 기념품을 사는 시간은 무시한다. 같은 가게를 두 번 이상 들르면 처음 들렀을 때만 산다. |
입력은 다음 형식으로 주어진다.
\(H\) \(W\) \(K\)
\(S_1\)
\(S_2\)
\(\vdots\)
\(S_H\)
- 입력은 \(1+H\)줄이다.
- 첫째 줄에 정수 \(H\), \(W\), \(K\)가 공백 하나로 구분되어 주어진다.
- 이어지는 \(H\)줄에 각각 길이 \(W\)의 문자열이 공백 없이 주어지고, 칸의 정보를 나타낸다. 북쪽에서 \(i\)번째, 서쪽에서 \(j\)번째 칸을 \((i, j)\)라 한다(\(1 \le i \le H\), \(1 \le j \le W\)).
- \(i\)번째 줄의 \(j\)번째 문자는, 칸 \((i, j)\)가 길 또는 국제공항이면 ., 주택이면 # 이다. 기념품 가게이면 \(1, 2, \ldots, 9\) 중 하나이고, 그 가게에서 살 수 있는 기념품 개수를 나타낸다.
- JOI 군이 처음에 있는 가장 북서쪽 칸은 길임이 보장된다. 국제공항에 도달할 수 있음도 보장된다.
- \(2 \le H \le 50\)
- \(2 \le W \le 50\)
- \(1 \le K \le 3\)
다음 형식으로 출력한다.
첫째 줄에 JOI 군이 살 수 있는 기념품 개수의 최댓값을 출력한다.
남쪽으로 \(3\)번 가 칸 \((4, 1)\)의 가게에서 산 뒤, 남쪽으로 \(1\)번·동쪽으로 \(3\)번 가고, 북쪽으로 \(2\)번 가 칸 \((3, 4)\)의 가게에서 산다. 마지막으로 남쪽으로 \(2\)번 가 국제공항에 도착하면 합계 \(11\)개를 살 수 있다.