T580717 「2025 扬大ACM选拔赛」G - Reach for the Moon

Mokou is given $n$ integer points $(x_i, y_i)$ in a 2D plane. In addition, She can freely add $m$ integer points. After freely adding $m$ points, Mokou should select several integer points from the $n + m$ points to form a sequence such that: - The Euclidean distance between any two adjacent points in the sequence is exactly $1$; - Both the $x$-coordinates and $y$-coordinates are **non-decreasing**. That is, either $x_{i + 1}-x_i = 1,y_{i + 1}=y_i$ or $y_{i + 1}-y_i = 1,x_{i + 1}=x_i$. Mokou wants to know the **maximum length** of the sequence that meets the conditions.

The first line contains two integers $n, m$ ($1 \le n \le 500$, $0 \le m \le 100$) —— the initial number of points and the number of addional points Mokou can freely add. For the following $n$ lines, the $i$-th line contains two integer $x_i, y_i$ ($1 \le x_i, y_i \le 10^9$) —— the coordinates of $i$-th point. It is guaranteed that **all given points are distinct**. For freely added integer points, their coordinates are unrestricted.

Output one integer, denoting the **maximum length** of the sequence that meets the conditions.

For the sample test case, one possible solution is as follows:  The blue points $(3, 2)$ and $(5,4)$ are freely added, Mokou can select points $(1, 2)$, $(2,2)$, $(3,2)$, $(3, 3)$, $(4,3)$, $(5,3)$, $(5,4)$, $(5, 5)$ to form a sequence that meets the conditions. So the answer is $8$.