Optimal Waterway Irrigation

In a mountainous region, people have long suffered from water scarcity affecting their crop yields. Recently, the government announced a plan to divert water from a lake at the mountain top to their village by digging a waterway. However, the water is extremely limited and different areas have different land values. Moreover, while water can come from areas not directly swept by a river, it cannot be routed from far away.

You are given a grid of size \(N \times N\) representing the mountain. The lake is located at coordinate \((x,y)\) (1-indexed), and for each cell you are provided its elevation and its land value. A waterway (or river) may be carved starting at the lake. The waterway must be a single, non-branching path that moves in the four cardinal directions and always goes from a cell of higher elevation to a cell of strictly lower elevation (i.e. water flows downhill).

Once a waterway is dug, land can be irrigated if it is within \(R\) cells (using Chebyshev distance, i.e. including diagonal neighbors) of any cell on the waterway. Note: Even the cells through which the waterway runs can be optionally considered for irrigation. However, due to limited water, at most \(M\) cells can be irrigated. If the total number of cells within distance \(R\) exceeds \(M\), then only the \(M\) cells with the highest land values are irrigated.

Your task is to determine the optimal way to carve a waterway (i.e. choosing a valid path starting at the lake) so that the total irrigated land value is maximized. The irrigated value is computed by summing the land values of the chosen irrigated cells (i.e. the top \(M\) valued cells in the union of all cells that lie within a Chebyshev distance of \(R\) from a cell on the waterway, or all if the count is less than or equal to \(M\)).

Input: The first line contains three integers \(N\), \(M\) and \(R\). The second line contains two integers \(x\) and \(y\) denoting the lake's coordinates (1-indexed). The next \(N\) lines each contain \(N\) integers describing the elevation of each cell. The following \(N\) lines each contain \(N\) integers describing the land value of each cell.

Output: Output a single integer, the maximum total irrigated land value achievable.

Constraints: It is guaranteed that a valid waterway path exists. You may assume the grid size is small enough to allow exhaustive search.

Note: For two cells \((i_1,j_1)\) and \((i_2,j_2)\), their Chebyshev distance is given by \(\max(|i_1-i_2|,|j_1-j_2|)\).

inputFormat

The input begins with a line containing three integers \(N\), \(M\) and \(R\) where \(N\) is the grid size and \(M\) is the maximum number of cells that can be irrigated, and \(R\) is the irrigation radius.

The second line contains two integers \(x\) and \(y\) specifying the 1-indexed coordinates of the lake.

The next \(N\) lines each contain \(N\) integers representing the elevation of the grid cells.

The following \(N\) lines each contain \(N\) integers representing the land values of the grid cells.

outputFormat

Output a single integer representing the maximum total land value that can be obtained by selecting up to \(M\) irrigated cells from the area covered by the waterway (including its Chebyshev \(R\)-neighborhood), following an optimal waterway path.

sample

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

11