16753번 - Maja 다국어

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

Maja will start her journey from her hive, which is located in the field in the A^th row and 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), all the pollinated flowers will disappear and C_i,j new unpollinated flowers will grow on that field.

Since Maja can't fly forever, she will get tired after 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 steps and ends her journey back at her hive?

The first line contains positive integers N, M (2 ≤ N, M ≤ 100), A (1 ≤ A ≤ N), B (1 ≤ B ≤ M) and K (2 ≤ K ≤ 10⁹). K will always be even.

N lines follows, each containing M integers describing amount of flowers C_i,j (0 ≤ C_i,j ≤ 10⁹) located in i^th row and j^th column.

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

Print the number from the task statement.

Clarification of sample tests:

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

In the second sample Maja start from the field (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) twice, each time pollinating 5 flowers on that field.