Maximum Wealth on a Hexagonal Grid

You are given a hexagonal grid with R rows and C columns, where each cell contains a wealth value. The grid is arranged such that neighboring cells differ based on the parity of the row index. Specifically, for a cell at position \( (i,j) \), its neighbors are determined by whether \( i \) is even or odd. Your task is to determine the maximum sum of wealth achievable by visiting exactly \( K \) consecutive cities (cells), starting at any cell and at each step moving to an adjacent unvisited cell.

Neighbor Rules:

• If \( i \) is even, the neighbors of \( (i,j) \) are \( (i-1,j-1), (i-1,j), (i,j-1), (i,j+1), (i+1,j-1), (i+1,j) \) (if they exist).
• If \( i \) is odd, the neighbors of \( (i,j) \) are \( (i-1,j), (i-1,j+1), (i,j-1), (i,j+1), (i+1,j), (i+1,j+1) \) (if they exist).

You must select a path of exactly \( K \) cells, where the path is a sequence of moves from one cell to an adjacent cell without revisiting any cell. Compute the maximum possible sum of the wealth values along such a path.

inputFormat

The input is read from stdin and has the following format:

R C
row1
row2
...
rowR
K

Where:

• R and C are integers representing the number of rows and columns.
• Each row contains C integers separated by spaces representing the wealth values in that row.
• K is an integer representing the number of cities to visit.

outputFormat

The output is a single integer written to stdout representing the maximum wealth sum achievable by visiting exactly \( K \) consecutive cities in accordance with the movement restrictions.

## sample

4 4
1 2 3 4
8 7 6 5
9 1 4 7
3 2 5 6
3

24