Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
The Delivery of Control
Time Limit: 10000MSMemory Limit: 65536K
Total Submissions: 219Accepted: 73
Case Time Limit: 3000MS

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

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator