P8816 [CSP-J 2022] Ascending Point Sequence

On a two-dimensional plane, you are given $n$ integer points $(x_i, y_i)$. In addition, you may freely add $k$ integer points. After adding $k$ points, you need to select some integer points from the $n + k$ points to form a sequence such that the Euclidean distance between any two adjacent points in the sequence is exactly $1$, and both the $x$-coordinate and the $y$-coordinate 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$. Please output the maximum possible length of such a sequence.

The first line contains two positive integers $n, k$, representing the number of given integer points and the number of integer points you may freely add. The next $n$ lines each contain two positive integers $x_i, y_i$, representing the coordinates of the $i$-th given point.

Output one integer representing the maximum length of a sequence that satisfies the requirements.

**【Sample \#3】** See `point/point3.in` and `point/point3.ans` in the attachments. In the third sample, $k = 0$. **【Sample \#4】** See `point/point4.in` and `point/point4.ans` in the attachments. **【Constraints】** It is guaranteed that for all testdata: $1 \leq n \leq 500$, $0 \leq k \leq 100$. For all given integer points, $1 \leq x_i, y_i \leq {10}^9$, and all given points are distinct. For the integer points you add freely, the coordinates have no restrictions. | Test Point ID | $n \leq$ | $k \leq$ | $x_i, y_i \leq$ | | :-----------: | :-----------: | :-----------: | :-----------: | | $1 \sim 2$ | $10$ | $0$ | $10$ | | $3 \sim 4$ | $10$ | $100$ | $100$ | | $5 \sim 7$ | $500$ | $0$ | $100$ | | $8 \sim 10$ | $500$ | $0$ | ${10}^9$ | | $11 \sim 15$ | $500$ | $100$ | $100$ | | $16 \sim 20$ | $500$ | $100$ | ${10}^9$ | Translated by ChatGPT 5