Minimum Warehouses for Building Coverage

You are given a city grid of dimensions \(n\) rows and \(m\) columns. Certain cells in this grid contain buildings. Your task is to determine the minimum number of warehouses that must be placed such that every building is within a distance \(r\) from at least one warehouse. The distance is measured using the Euclidean metric, i.e., the distance between two points \((x_1, y_1)\) and \((x_2, y_2)\) is given by \(\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\).

The warehouses can be placed at any grid cell (with integer coordinates between \(0\) to \(n-1\) for rows and \(0\) to \(m-1\) for columns). Note that a warehouse covers a building if the Euclidean distance between the warehouse and the building is less than or equal to \(r\). Use a greedy strategy to place warehouses so that in each step you cover as many uncovered buildings as possible.

inputFormat

The input is read from standard input. The first line contains four integers: \(n\), \(m\), \(r\) and \(k\), where \(n\) is the number of rows, \(m\) is the number of columns, \(r\) is the warehouse coverage radius, and \(k\) is the number of buildings. This is followed by \(k\) lines, each containing two integers \(x\) and \(y\) representing the coordinates of a building.

Note: Coordinates are zero-indexed and valid grid positions are \(0 \le x < n\) and \(0 \le y < m\).

outputFormat

Output a single integer representing the minimum number of warehouses required so that every building is covered (i.e. is within a distance \(r\) of at least one warehouse). The output should be printed to standard output.

## sample

5 5 2 3
1 1
4 4
2 3

2

</p>