Problem Z
Economical Coverage

Image by Ilya Sedykh

Providing wireless network coverage for a large office can be tricky. In this problem you are asked to set up wireless network coverage for an entire office floor plan. The floor plan can be viewed as an $N\times M$ grid. Each grid cell represents a single office. Each pair of adjacent offices (cells that share a side) are connected by a corridor. You may install routers in some of the offices. Each installed router provides wireless network for the (at most four) corridors that are incident to the office where the router is located. Installing routers at different offices may have different costs.

However, some issues arise. If neither of the two offices incident to a corridor has a router, the corridor would have weak signal. If both of the two offices incident to a corridor have a router, the corridor would have conflicting signals that would cause both routers to be inaccessible from the corridor. (Unfortunately the routers available are pretty old models that do not collaborate very well.) Consequently, for every corridor that has either weak or conflicting signal, you must additionally install a cellular hub, which provides separate wireless service (that uses cellular network and is independent of the routers). Each cellular hub is sold for $K$ dollars.

Find the minimum total cost to set up a wireless network that covers every corridor.

Input

The first line of the input has three integers $N$, $M$ ($2\le N,M\le 40$), and $K$ ($0\le K\le 200$). The next $N$ lines contains $M$ non-negative integers each. The $j$-th integer on the $i$-th line is the cost (in dollars) of installing a router in the office at the $i$-th row, $j$-th column of the floor plan. All costs are no larger than $200$.

Output

Output the minimum total cost (in dollars) to provide a wireless network that covers every corridor.

2 3 4
10 1 3
0 1 20

9

2 3 100
10 1 10
10 1 10

21

2 2 1
10 10
10 10

4