题目描述
蜜蜂 Maja 在一个神奇的牧场里为花朵传粉。牧场可用一个 $N \times M$ 的矩阵表示。在第 $i$ 行第 $j$ 列有 $C_{i,j}$ 朵未传粉的花。
Maja 从位于第 $A$ 行第 $B$ 列的蜂巢出发,并前往牧场的一些区域后返回。Maja 可以在 $1$ 步内从当前区域前往相邻的区域(即位于原区域的左、右、上或下方的区域),但不会离开牧场。每当 Maja 经过一个区域,它将会将该区域所有未传粉的花全部进行传粉。但牧场是神奇的!Maja 在离开区域 $(i,j)$ 后,所有传过粉的花将全部消失,而紧接着将会有 $C_{i,j}$ 朵未传粉的花重新生长。
由于 Maja 不能一直飞下去,因此它将在 $K$ 步后感到劳累。Maja 在 $K$ 步内从蜂巢出发并返回的途中,最多能为多少朵花传粉?
输入格式
第一行输入正整数 $N,M,A,B,K$。
接下来的 $N$ 行,每行输入 $M$ 个整数表示区域 $(i,j)$ 的花的数量 $C_{i,j}$。
蜂巢所在区域不会有任何花朵生长。
输出格式
输出 Maja 在 $K$ 步内从蜂巢出发并返回的途中,被传粉的花的最大数量。
样例 #1
样例输入 #1
2 2 1 1 2
0 1
2 10
样例输出 #1
2
样例 #2
样例输入 #2
2 2 1 1 4
0 5
5 10
样例输出 #2
20
样例 #3
样例输入 #3
3 3 2 2 6
5 1 0
1 0 3
1 3 3
样例输出 #3
15
提示
样例 1 解释
Maja 从 $(1,1)$ 开始,先向下飞行,为 $2$ 朵花传粉,然后再返回。
样例 2 解释
Maja 从 $(1,1)$ 开始,依次向右、下、上、左飞行。由于 Maja 经过了 $(1,2)$ 两次,因而它每经过一次,便可为 $5$ 朵花传粉。
数据规模与约定
对于 $40\%$ 的数据,$K \le 10^4$。
对于 $100\%$ 的数据,$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$。