题目描述

一个 $N$ 行 $M$ 列方格组成的迷宫，迷宫中的方格有些是障碍，有些方格放着有若干数量的宝物，障碍处无法通过，迷宫外被一圈障碍包围。已知迷宫左上角方格是第一行第一列的格子，在迷宫中只能上下左右四个方向移动到不是障碍的方格，并且每次只能移动一步，从一个方格移动到上下左右相邻的方格需要一个单位时间。现在从迷宫 $sx$ 行 $sy$ 列处的方格出发去获取宝物，获取宝物的规则如下：

• 经过有宝物的方格时，可以取一些宝物，也可以不取；
• 取走某个方格的宝物后，就可以前往其他有宝物的方格继续取宝物；
• 有宝物的方格每过一个单位时间就有一个宝物消失，直到该方格所有宝物消失为止；
• 在方格取一个宝物需要耗费一个单位时间，这就意味着在一个有宝物的方格取宝物的过程中，该方格中的宝物也会按照上一条规则消失。假如该方格有 $k$ 个宝物，可知在时间允许的情况下，最多可以取走 $\lceil \displaystyle{\frac{k}{2}} \rceil$（向上取整）个宝物，同时也耗费这样多的单位时间。

请问在 $T$ 单位时间内，能获取的所有宝物数量的最大值。

输入格式

第 $1$ 行是五个正整数 $N,M,sx,sy,T$；

接下来有 $N$ 行，每行 $M$ 个整数。这 $N$ 行中第 $i$ 行 $j$ 列的整数 $k_{ij}$ 用来描述迷宫内第 $i$ 行 $j$ 列方格的情况：$-1$ 表示该方格是障碍，$0$ 表示该方格没有宝物，正整数则表示该方格宝物的数量；

数据间用一个空格隔开。

输出格式

一个整数，就是在 $T$ 单位时间内，能获取的宝物数量的最大值。

输入输出样例

4 5 1 1 20
0 -1 4 -1 3
1 -1 3 2 -1
2 6 0 -1 15
3 3 4 15 9

7

说明/提示

👀️ 对于 $100\%$ 的数据，$1 \leq N,M,T \leq 100，1 \leq sx \leq N，1 \leq sy \leq M，-1 \leq k_{ij} \leq 200$，从出发点出发能够到达的有宝物的方格数量不超过 $50$，出发点不是障碍。