Description

People living in mountainous areas have long been troubled by the lack of water sources, which prevents their farmland from achieving good harvests. Recently, good news arrived: the govern$$ment will provide funds to dig a canal to bring water from the only source—a lake on the mountain top—down to their village. People were overjoyed; their fields could finally yield a good harvest.

However, when digging the canal, they encountered a problem: how should they dig to obtain the greatest harvest?

Note that the water at the mountain top is very limited and cannot irrigate every region. Moreover, different regions have different levels of soil fertility. Although irrigation is not limited only to regions that the river passes through, water cannot be brought from very far away. You must find a way to solve this problem.

First, you can divide the mountainous area into an $N \times N$ grid, with the lake located at $(x,y)$ (indices start from $1$). The elevation of each cell is known (the excavated river can only flow strictly from higher elevation to strictly lower elevation), and the value of each cell of land is also known.

At the same time, note that the river is not allowed to have branches (tributaries). At most $M$ plots can be irrigated, and irrigated plots must be within $R$ cells of the river (including diagonals).

Note: Land that the river passes through still retains its value; you may choose whether to irrigate it.

Your goal is to find the best way to dig the river such that the total value of irrigated land is maximized.

Input Format

The first line contains three integers $N,M,R\ (1 \le N \le 20,1 \le M \le \min\{N^2,100\},1 \le R \le \min\{N-1,5\})$, giving the side length of the grid, the maximum number of plots that can be irrigated, and the maximum allowed distance from an irrigated plot to the river.

The second line contains two integers $x,y\ (1 \le x,y \le N)$, giving the location of the lake.

Then follows an $N \times N$ matrix $A\ (1 \le A_{i,j} \le 200)$, where $A_{i,j}$ denotes the elevation of $(i,j)$.

Then follows an $N \times N$ matrix $V\ (1 \le V_{i,j} \le 200)$, where $V_{i,j}$ denotes the value of $(i,j)$.

Output Format

Output a single integer, the maximum total value computed by your program.

5 5 1
3 3
1 1 1 1 1
1 6 9 5 1
1 3 10 3 1
1 2 1 2 1
1 1 1 1 1

4 1 1 1 2
1 1 1 1 1
1 2 3 1 2
1 2 1 1 1
1 1 1 1 1

12

Hint

Sample explanation:

An optimal solution is as follows.

River flow:

Irrigated plots:

Translated by ChatGPT 5