#3127. 「COCI 2018.11」Maja

内存限制:64 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

译自 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

样例输出 1

2

样例解释 1

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

样例输入 2

2 2 1 1 4
0 5
5 10

样例输出 2

20

样例解释 2

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

样例输入 3

3 3 2 2 6
5 1 0
1 0 3
1 3 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