COCI '18 Contest 2 #4 Maja

Points: 15 (partial)

Time limit: 1.0s

Memory limit: 64M

Problem type

Maja the Bee pollinates flowers in a magical meadow. The meadow can be represented as a matrix of $N$ ~N~ rows and $M$ ~M~ columns. In $i^{th}$ ~i^{th}~ row and $j^{th}$ ~j^{th}~ column there are $C_{i,j}$ ~C_{i,j}~ unpollinated flowers.

Maja will start her journey from her hive, which is located in the field in the $A^{th}$ ~A^{th}~ row and $B^{th}$ ~B^{th}~ column. In several steps, she will visit some fields of the meadow and then return back to her hive. From each field, Maja can move to one of its adjacent cells in one of the following directions: left, right, up or down. Also, Maja will never leave the meadow. Each time Maja flies over some field, she pollinates all unpollinated flowers growing on the field. But the meadow is magical! As soon as Maja leaves the field $(i, j)$ ~(i, j)~, all the pollinated flowers will disappear and $C_{i,j}$ ~C_{i,j}~ new unpollinated flowers will grow on that field.

Since Maja can't fly forever, she will get tired after $K$ ~K~ steps and gladly tell her adventurous story to her bee friends. What is the maximal number of flowers Maja can pollinate if she makes exactly $K$ ~K~ steps and ends her journey back at her hive?

Input

The first line contains positive integers $N, M$ ~N, M~ $(2 \le N, M \le 100)$ ~(2 \le N, M \le 100)~, $A$ ~A~ $(1 \le A \le N)$ ~(1 \le A \le N)~, $B$ ~B~ $(1 \le B \le M)$ ~(1 \le B \le M)~ and $K$ ~K~ $(2 \le K \le 10^9)$ ~(2 \le K \le 10^9)~. $K$ ~K~ will always be even.

$N$ ~N~ lines follows, each containing $M$ ~M~ integers describing amount of flowers $C_{i,j}$ ~C_{i,j}~ $(0 \le C_{i,j} \le 10^9)$ ~(0 \le C_{i,j} \le 10^9)~ located in $i^{th}$ ~i^{th}~ row and $j^{th}$ ~j^{th}~ column.

The field containing the hive won't have any flowers on it.

Output

Print the number from the task statement.

Scoring

In test cases worth 40% of the total points it will hold $K \le 10\,000$ ~K \le 10\,000~.

Sample Input 1

2 2 1 1 2
0 1
2 10

Sample Output 1

Explanation for Sample Output 1

In the first sample Maja starts from the field $(1,1)$ ~(1,1)~, flies to the field below, pollinates $2$ ~2~ flowers there, and returns back to the hive.

Sample Input 2

2 2 1 1 4
0 5
5 10

Sample Output 2

Explanation for Sample Output 2

In the second sample Maja starts from the field $(1,1)$ ~(1,1)~ and can pollinate flowers moving as follows: she moves right, then down, then up and then left. Notice that Maja visited the field $(1,2)$ ~(1,2)~ twice, each time pollinating $5$ ~5~ flowers on that field.

Sample Input 3

Sample Output 3

Comments

There are no comments at the moment.