P7311 [COCI 2018/2019 #2] Maja

The bee Maja is pollinating flowers in a magical meadow. The meadow can be represented as an $N \times M$ matrix. In row $i$ and column $j$, there are $C_{i,j}$ unpollinated flowers. Maja starts from the beehive located at row $A$ and column $B$, travels to some areas of the meadow, and then returns. In $1$ step, Maja can move from the current area to an adjacent area (the area to the left, right, above, or below), but it will not leave the meadow. Each time Maja passes through an area, it pollinates all currently unpollinated flowers in that area. But the meadow is magical: after Maja leaves area $(i,j)$, all pollinated flowers there disappear, and then $C_{i,j}$ unpollinated flowers immediately grow back. Since Maja cannot fly forever, it will get tired after $K$ steps. What is the maximum number of flowers Maja can pollinate while starting from the hive and returning to it within $K$ steps?

The first line contains positive integers $N, M, A, B, K$. The next $N$ lines each contain $M$ integers, where the value for area $(i,j)$ is the number of flowers $C_{i,j}$. No flowers grow in the area where the beehive is located.

Output the maximum number of flowers Maja can pollinate while starting from the hive and returning to it within $K$ steps.

#### Sample 1 Explanation Maja starts at $(1,1)$, first flies downward to pollinate $2$ flowers, and then returns. #### Sample 2 Explanation Maja starts at $(1,1)$ and flies right, down, up, and left in order. Since Maja passes through $(1,2)$ twice, each time it passes, it can pollinate $5$ flowers. #### Constraints For $40\%$ of the testdata, $K \le 10^4$. For $100\%$ of the testdata, $2 \le N, M \le 100$, $1 \le A \le N$, $1 \le B \le M$, $2 \le K \le 10^9$, $0 \le C_{i,j} \le 10^9$, and $K \bmod 2 = 0$. #### Notes **The score of this problem follows the original COCI setting, with a full score of $110$.** **This problem is translated from [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #2](https://hsin.hr/coci/archive/2018_2019/contest2_tasks.pdf) _T4 Maja_.** Translated by ChatGPT 5