Maximizing Enclosed Weight Sum by an Ant’s Path

An ant starts at some vertex on an n × m chessboard where each cell has an integer weight. Initially the ant faces north. It then walks along grid edges (only turning at vertices) and makes turns according to a fixed pattern. The turn sequence is fixed as follows:

• First, two consecutive right turns;
• If k = (number of left turns)/2 is zero, the ant makes no left turns. In this case the full turning sequence is: right turn, right turn, right turn. Thus the ant makes 3 turns and walks 4 segments, forming a rectangle.
• If k = 1 (when the input k is 1) then the ant’s turning sequence is: right, right, left, left, right, right, right. In general, when k ≥ 1 the ant first makes an initial pair of right turns, then for k-1 times it makes a pair of left turns immediately followed by a pair of right turns, and finally it makes a pair of left turns followed by two right turns and one additional right turn. (In this problem we only require you to handle the cases k = 0 and k = 1.)

When the ant walks, it does not revisit any vertex other than the starting vertex at the end, and it never turns twice in a row at the same vertex. Although the turn directions are fixed, the lengths of the segments between turns (which are positive integers) are not given. You may choose these lengths arbitrarily under the following conditions:

1. The ant always turns at grid vertices (vertices have integer coordinates, with x between 0 and m and y between 0 and n).
2. The entire path must lie on the chessboard grid and the ant must return to its starting vertex at the end.
3. The resulting closed polygon is simple (its vertices, except for the starting/ending vertex, are all distinct).

The enclosed region is the area inside the polygon. Its weight is defined as the sum of the weights of all cells that lie completely inside the polygon. (A cell is considered inside if its entire area is contained in the polygon.)

Given the board dimensions, the weight of each cell, and the value of k (which is equal to the number of left turns divided by 2), determine the maximum possible weight sum of the enclosed region that the ant can achieve by choosing appropriate segment lengths and the starting position. For this problem, you only need to handle the cases where k = 0 or k = 1.

---

Problem Summary

• If k = 0: The ant’s path is a rectangle. In this case, the problem reduces to finding the maximum sub-rectangle sum of the board.
• If k = 1: The ant’s path forms a polygon which can be considered as an outer rectangle with a rectangular hole cut from the top‐right corner. More precisely, if you choose an outer rectangle with top‐left vertex at (T,L) and bottom‐right vertex at (B,R) (with H = B − T and W = R − L), then by selecting parameters b, c, d (all positive) such that 1 ≤ b ≤ W − 2, 1 ≤ c ≤ H − 1, and 1 ≤ d ≤ W − b − 1, the polygon is defined as the outer rectangle minus the hole whose top‐right corner has size c × d and whose left boundary is offset by b from the left of the outer rectangle. (The hole will appear in the top–right portion of the outer rectangle.) The weight of the enclosed region is the sum of the weights of cells inside the outer rectangle minus the sum of the weights of the cells inside the hole. Your task is to choose the position of the outer rectangle and parameters b, c, d (if k = 1) to maximize this value.

Note: The board’s rows are numbered from 0 to n-1 and columns from 0 to m-1. A sub-rectangle is defined by choosing two distinct horizontal grid lines and two distinct vertical grid lines.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 20), the number of rows and columns of the chessboard.

The next n lines each contain m integers. The j-th integer in the i-th line is the weight of the cell in row i and column j. The absolute value of the weights does not exceed 10⁴.

The last line contains an integer k (0 ≤ k ≤ 1) which is equal to (number of left turns)/2. (For this problem, k will be either 0 or 1.)

outputFormat

Output a single integer: the maximum possible sum of weights of the cells inside a closed polygon constructed as described by the ant’s path.

sample

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

29

</p>