Problem Description

JOI-kun has come to Australia for a trip and has enjoyed sightseeing at various places. Finally, the day of his return has arrived. Now, JOI-kun is in the town where the international airport is located, which is the departure point for his flight back home. The town is divided into grids, and each grid contains a road, a souvenir shop, a residential area, or the international airport. JOI-kun starts from the northwestmost grid and aims to reach the international airport in the southeastmost grid.

JOI-kun can move to an adjacent grid, but he cannot enter a grid with a residential area. Also, to catch his flight on time, he can only move to the east or south of his current grid. However, due to some extra time available, he can move to the north or west of his current grid up to $ K $ times.

When JOI-kun enters a grid with a souvenir shop, he buys souvenirs for his friends in Japan. JOI-kun has thoroughly researched the souvenir shops, so he knows how many souvenirs he can buy at each shop. Write a program to determine the maximum number of souvenirs JOI-kun can purchase.

Note that the time spent buying souvenirs is negligible, and he only buys souvenirs the first time he visits a shop.

Input Format

The input consists of $ 1 + H $ lines.

The first line contains three integers $ H, W, K $ ($2 \leq H \leq 50$, $2 \leq W \leq 50, 1 \leq K \leq 3$) separated by spaces.

The following $ H $ lines each contain a string of $ W $ characters, representing the information of the grids. The $ i $-th line from the north and the $ j $-th column from the west is represented as $ (i, j) $ ($1 \leq i \leq H$, $1 \leq j \leq W$). The $ j $-th character in the $ i $-th line is . if the grid $ (i, j) $ is a road or the international airport, # if it is a residential area, and 1, 2, ..., 9 if it is a souvenir shop, indicating the number of souvenirs that can be bought there.

In the given input data, it is guaranteed that the northwestmost grid where JOI-kun starts is a road, and it is guaranteed that JOI-kun can reach the international airport.

Output Format

Output a single integer representing the maximum number of souvenirs JOI-kun can purchase.

Sample Input and Output

Sample Input #1

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

Sample Output #1

11

Sample Input #2

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

Sample Output #2

27

Notes/Hints

Sample Explanation 1

In sample input #1, JOI-kun moves south 3 times to the grid $ (4, 1) $ and buys souvenirs. Then, he moves south once and east 3 times, and from there, he moves north 2 times to the grid $ (3, 4) $ to buy souvenirs. Finally, he moves south 2 times to reach the international airport, purchasing a total of 11 souvenirs.

见题面 Input 部分

见题面 Output 部分