Description

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?

Input Format

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 Format

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

2 2 1 1 2
0 1
2 10

2

2 2 1 1 4
0 5
5 10

20

3 3 2 2 6
5 1 0
1 0 3
1 3 3

15

Hint

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 CONTEST #2 T4 Maja.

Translated by ChatGPT 5