Diamonds

Consider a planar grid with $M$ rows and $N$ columns. It has exactly $MN$ intersections, each identified by a coordinate pair $(i, j)$ with $i = 0, 1, \ldots, N-1$ (the column, or $x$-coordinate) and $j = 0, 1, \ldots, M-1$ (the row, or $y$-coordinate).

Now place $K \le MN$ points on $K$ distinct intersections.

A diamond $D(i, j, r)$ is centred at intersection $(i, j)$ and is a square of diagonal length $2r$ rotated $45^\circ$; its radius $r$ is any integer with $r \ge 1$. Equivalently, $D(i, j, r)$ covers exactly the points whose Manhattan distance from the centre is at most $r$, that is, every point $(x, y)$ with $|x - i| + |y - j| \le r$.

For each $P_{\min} = 1, 2, \ldots, K$, find the smallest radius $R_{\min}(P_{\min})$ such that a diamond of that radius is guaranteed to cover at least $P_{\min}$ points no matter which intersection its centre is placed on. In other words, $R_{\min}(P_{\min})$ is the smallest $r$ for which the worst case (the minimum, over all centres, of the number of covered points) is at least $P_{\min}$.

Let $P_{\max}(P_{\min})$ be the largest number of points that any single diamond of radius $R_{\min}(P_{\min})$ can cover.

For example, take five points at $(0,0)$, $(4,0)$, $(2,2)$, $(0,4)$, and $(4,4)$ on a grid of $5$ rows and $7$ columns. The diamond $D(2,4,1)$ covers no point, $D(2,1,2)$ covers one point, and $D(3,3,4)$ covers four points.

Line 1 contains the number of rows $M$ and the number of columns $N$.

The remaining lines list the $K$ points ($K \le MN$). Each point is given as a pair of integers: its $x$-coordinate followed by its $y$-coordinate. Points may be spread across one or more lines, and all values on a line are separated by one or more whitespace characters (spaces or tabs).

You may assume $1 \le M \le 100$ and $1 \le N \le 100$. Any point lying outside the grid (that is, $x < 0$, $x > N-1$, $y < 0$, or $y > M-1$) is invalid and must be discarded.

Print a header line containing the three column titles Pmin, Rmin(Pmin), and Pmax(Pmin), then one line for each qualifying value of $P_{\min}$.

For a value of $P_{\min}$, output the triple $P_{\min}$, $R_{\min}(P_{\min})$, $P_{\max}(P_{\min})$ only if a diamond of radius $R_{\min}(P_{\min})$ is guaranteed to cover exactly $P_{\min}$ points. When two consecutive values share the same radius (for example $R_{\min}(2) = R_{\min}(3)$), only the larger one qualifies, so the smaller value produces no line.

Each value is right-aligned so that its last character lines up with the last character of that column's heading, and columns are separated by two spaces.