题目描述

译自 COCI 2018/2019 Contest #2 T4「Maja」

Maja 是一只蜜蜂，她要给一片魔法草地授粉，这片草地是一个 $N$ 行 $M$ 列的网格。第 $i$ 行 $j$ 列的田地上有 $C_{ij}$ 朵未授粉的花。

Maja 的蜂房在第 $A$ 行 $B$ 列，她会从她的蜂房出发，走到一个与之四联通的蜂房，但始终不能离开这片草地。当她飞到一片草地，就会给这片草地的花授粉。但是因为这是一片魔法草地，当她离开后这些花朵就会消失，并再次生长出 $C_{ij}$ 朵未授粉的花！

Maja 总共飞 $K$ 步之后就要退休了，她想知道如果她恰飞了 $K$ 步后回到蜂房，能够最大化的过程中授粉花朵数量是多少？

输入格式

第一行输入五个正整数 $N, M, A, B, K$，表示行数、列数、蜂房位置和步数，保证 $K$ 是偶数。

接下来 $N$ 行每行 $M$ 个非负整数 $C_{ij}$，表示对应位置的花朵数量。保证 $C_{AB}=0$。

输出格式

一个整数，表示最大化的授粉花朵数量。

样例 1

2 2 1 1 2
0 1
2 1

2

Maja 从 $(1,1)$ 位置出发，第一步向下，对 $2$ 朵花授粉，第二步向上返回。

2 2 1 1 4
0 5
5 10

20

Maja 先向右，然后向下、向上、向左。注意到 $(1, 2)$ 位置的花朵被授粉了两次。

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

15

数据范围与提示

对于 $40\%$ 的数据，保证 $K \le 10^4$。

对于 $100\%$ 的数据，保证

• $1\le N, M \le 100$
• $1\le A\le N, 1\le B\le M$
• $2\le K \le 10^9$
• $0\le C_{ij} \le 10^9$