Logo Universal Online Judge

UOJ

时间限制:2 s 空间限制:64 MB
统计

题目描述

蜜蜂 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$。