NM and K (1)

Interview

Time limit2sMemory limit512 MB

Summary

Choose exactly K non-adjacent cells from an N by M grid, at most 10 by 10, to maximize the sum of their values.

Level: Hard8 of 10
Topics: Dynamic programming, Bit manipulation, Brute force, Implementation
Solved: No attempts yet

Problem

Each cell of an N×M grid contains an integer. You will choose K cells from this grid and find the maximum possible sum of the numbers in the chosen cells. However, no two chosen cells may be adjacent. When the cell in row r and column c is written as (r, c), the cells (r-1, c), (r+1, c), (r, c-1), and (r, c+1) are adjacent to it.

Input

The first line gives N, M, and K. From the second line, N lines give the numbers in the grid.

Output

Print the maximum possible sum of the numbers in the chosen cells.

Constraints

1 ≤ N, M ≤ 10
1 ≤ K ≤ min(4, N×M)
Every number in the grid is an integer between -10,000 and 10,000 inclusive.
The input is always given so that K cells can be chosen.

Examples4

Example 1
Input
```
1 1 1
1
```
Expected output
```
1
```
Example 2
Input
```
2 2 2
1 2
3 4
```
Expected output
```
5
```
Example 3
Input
```
2 2 2
5 4
4 5
```
Expected output
```
10
```

Example 4

Input

5 5 3
1 9 8 -2 0
-1 9 8 -3 0
-5 1 9 -1 0
0 0 0 9 8
9 9 9 0 0

Expected output