Problem Description

Bee Maja is pollinating flowers in a magical pasture, which can be represented by an $N \times M$ matrix. In the $i$-th row and $j$-th column, there are $C_{i,j}$ unpollinated flowers.

Maja starts from the hive located at the $A$-th row and $B$-th column and travels to various areas of the pasture before returning. Maja can move to an adjacent area (left, right, up, or down from the current area) in one step, but it will not leave the pasture. Whenever Maja passes through an area, it pollinates all the unpollinated flowers in that area. However, the pasture is magical! After leaving area $(i,j)$, all pollinated flowers disappear, and $C_{i,j}$ unpollinated flowers regrow immediately.

Since Maja cannot fly indefinitely, it will become tired after $K$ steps. What is the maximum number of flowers Maja can pollinate within $K$ steps, starting from and returning to the hive?

Input Format

The first line contains positive integers $N, M, A, B, K$.

The next $N$ lines contain $M$ integers each, representing the number of flowers $C_{i,j}$ in area $(i,j)$.

The hive area will not have any flowers growing.

Output Format

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

Sample Input and Output

Sample Input #1

2 2 1 1 2
0 1
2 10

Sample Output #1

2

Sample Input #2

2 2 1 1 4
0 5
5 10

Sample Output #2

20

Sample Input #3

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

Sample Output #3

15

Notes/Hints

Sample 1 Explanation

Maja starts at $(1,1)$, flies down to pollinate 2 flowers, and then returns.

Sample 2 Explanation

Maja starts at $(1,1)$, flies right, down, up, and left. Since Maja passes through $(1,2)$ twice, it pollinates 5 flowers each time.

Data Constraints

For $40\%$ of the data, $K \le 10^4$.

For $100\%$ of the data, $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$, $K \bmod 2 = 0$.

Notes

This problem's score is set according to the original COCI contest, with a maximum score of $110$.

The problem is translated from COCI2018-2019 CONTEST #2 T4 Maja.

见题面 Input 部分

见题面 Output 部分