Description
The Gugoo Gang controls an area of N × M blocks in a city. To award Tom for his contribution to the Gugoo, the Boss decides to turn over part of the area under his control to Tom. The delivery is done according to the Gang's old tradition.
Tom is asked to start a trip at a cross in the city, take a ride along the streets, and finally get back to his start point within T minutes. In every minute Tom may move from one cross to an adjacent one. The blocks enclosed by his route are delivered to him. During the trip, Tom is not allowed to come back to a cross which he has already visited except the start point and once he reaches the start point his trip ends. If Tom fails to get back in time, he won't get any block. And he can not give up any blocks that is enclosed by his route.
As an environment protectionist, Tom assigns a satisfaction value to each block according to its greenness. He wants to maximize the sum of satisfaction values of his blocks.
Input
The first line contains three integers, N, M and T (1 ≤ N, M, T ≤ 20).
N × M integers follow which describe the satisfaction values of every block.
Output
One line contains the maximum sum.
Sample Input
4 4 10
-1 2 1 1
2 -1 0 2
3 1 -1 1
2 2 1 -1
Sample Output
10
