Problem Description

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.

Input Format

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 Format

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

8 2
3 1
3 2
3 3
3 6
1 2
2 2
5 5
5 3

8

4 100
10 10
15 25
20 20
30 30

103

Hint

【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.

Translated by ChatGPT 5