Optimal Water Tank Placement

You are given a rectangular garden of size \(y \times x\) cells and a set of \(n\) potential locations for placing water tanks. Your task is to choose exactly \(k\) locations among these potential sites such that the average Manhattan distance from every cell in the garden to its nearest water tank is minimized.

The average distance is computed as follows:

[ \text{Average} = \frac{1}{x \times y} \sum_{\text{cell} \in \text{garden}} d(\text{cell}, \text{nearest tank}) ]

Output the minimized average distance as an integer (the floor value of the computed average).

inputFormat

The input is given via standard input with the following format:

x y n
row1
row2
... (total y rows, each containing x integers separated by spaces)
potential_location1
potential_location2
... (total n lines, each with two integers representing 0-indexed row and column)
k

For example, a test case might look like:

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

outputFormat

The output is a single integer printed to standard output representing the minimal average distance (after flooring) from any cell in the garden to its nearest water tank.

## sample

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

2