Bee Maja Pollination

Maja the bee is on a mission to pollinate flowers in a magical pasture represented by an \(N\times M\) matrix. In cell \((i,j)\) there are \(C_{i,j}\) unpollinated flowers. Maja starts at the beehive located at cell \((A,B)\) (1-indexed) and must return to the hive within at most \(K\) steps.

In one step, Maja can move to one of the four adjacent cells (up, down, left, or right) and cannot leave the pasture. Whenever she enters a cell, she pollinates all unpollinated flowers there, earning an amount equal to \(C_{i,j}\). Due to the magic of the pasture, immediately after leaving a cell, all the pollinated flowers vanish and \(C_{i,j}\) new unpollinated flowers regrow in that cell. Since a cell’s flowers always regrow after Maja leaves, she can pollinate the same cell multiple times if she visits it repeatedly.

Your task is to help Maja maximize the total number of flowers she pollinates on a closed path that starts at the hive \((A,B)\), takes at most \(K\) steps (where each move counts as one step) and returns to the hive. Note that Maja does not get any reward for the starting cell at time 0, but if she visits it later during her path, she earns \(C_{A,B}\) at that visit.

inputFormat

The input begins with a line containing five integers \(N\), \(M\), \(K\), \(A\), and \(B\) representing the number of rows, columns, the maximum number of steps allowed, and the 1-indexed starting cell (hive) coordinates, respectively. The following \(N\) lines each contain \(M\) integers. The \(j\)-th integer in the \(i\)-th line indicates \(C_{i,j}\), the number of flowers in cell \((i,j)\).

It is guaranteed that \(K\) is a non-negative integer. Maja must return to the hive within at most \(K\) steps.

outputFormat

Output a single integer: the maximum number of flowers that Maja can pollinate while starting from and returning to the hive within \(K\) steps.

sample

3 3 4 2 2
1 2 3
4 5 6
7 8 9

28