JOI đến Úc du lịch và đã vui chơi, tham quan nhiều nơi. Cuối cùng, ngày trở về nước cũng đến. Hiện tại cậu đang ở thị trấn có sân bay quốc tế, nơi chuyến bay về nước của cậu sẽ khởi hành. Thị trấn được chia thành các ô theo các hướng đông, tây, nam, bắc; mỗi ô là đường đi, cửa hàng lưu niệm, nhà ở hoặc sân bay quốc tế. JOI xuất phát từ ô ở góc tây bắc và muốn đến sân bay quốc tế ở ô góc đông nam.

Từ ô hiện tại, JOI có thể đi sang một ô kề cạnh, nhưng không được vào ô có nhà ở. Để kịp giờ bay, cậu chỉ di chuyển sang ô phía đông hoặc phía nam. Tuy nhiên, do vẫn còn một chút thời gian dư, cậu được phép thực hiện tổng cộng tối đa \(K\) lần di chuyển sang ô phía bắc hoặc phía tây.

Khi vào một ô có cửa hàng lưu niệm, JOI sẽ mua quà cho các bạn ở Nhật Bản. Cậu đã tìm hiểu kỹ các cửa hàng, nên biết ở mỗi cửa hàng mình có thể mua bao nhiêu món quà. Hãy viết chương trình tính số món quà nhiều nhất mà JOI có thể mua.

Có thể bỏ qua thời gian mua sắm. Nếu đến cùng một cửa hàng từ hai lần trở lên, JOI chỉ mua quà trong lần ghé đầu tiên.

Yêu cầu

Tính số món quà nhiều nhất JOI có thể mua trên một hành trình hợp lệ từ góc tây bắc đến sân bay ở góc đông nam.

Dữ liệu vào

Dữ liệu vào gồm \(1+H\) dòng.

• Dòng đầu tiên chứa ba số nguyên \(H,W,K\) (\(2\le H\le50\), \(2\le W\le50\), \(1\le K\le3\)), cách nhau bởi dấu cách.
• Mỗi dòng trong \(H\) dòng tiếp theo chứa một xâu độ dài \(W\), mô tả các ô của thị trấn.

Gọi ô thứ \(i\) tính từ phía bắc và thứ \(j\) tính từ phía tây là \((i,j)\) (\(1\le i\le H\), \(1\le j\le W\)). Ký tự thứ \(j\) trên dòng thứ \(i\) của bản đồ có ý nghĩa như sau:

• .: ô \((i,j)\) là đường đi hoặc sân bay quốc tế.
• #: ô \((i,j)\) có nhà ở.
• Một trong các ký tự 1, 2, ..., 9: ô \((i,j)\) có cửa hàng lưu niệm; chữ số đó là số món quà có thể mua tại cửa hàng.

Dữ liệu bảo đảm ô ở góc tây bắc, nơi JOI bắt đầu, là đường đi. Dữ liệu cũng bảo đảm JOI có thể đến được sân bay quốc tế.

Dữ liệu ra

In ra một dòng chứa một số nguyên là số món quà nhiều nhất mà JOI có thể mua.

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

11

JOI đi về phía nam \(3\) lần và mua quà ở cửa hàng tại ô \((4,1)\). Sau đó, cậu đi thêm \(1\) lần về phía nam, \(3\) lần về phía đông, rồi \(2\) lần về phía bắc để mua quà ở cửa hàng tại ô \((3,4)\). Cuối cùng, cậu đi \(2\) lần về phía nam để đến sân bay quốc tế. Theo cách này, cậu mua được tổng cộng \(11\) món quà.

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

27