Background

$$\blue{They are coming.}$$ $$\purple{Assemble the army, take them out, leave none alive.}$$$$\blue{Yes!}$$

Problem Description

The situation on the Meow Planet’s border is getting more and more tense, leading to border conflicts. The commander-in-chief of the Meow Planet’s army, Xiao Yuan, immediately launches a military operation against Planet $Y$.

The entire universe can be viewed as a 2D Cartesian coordinate system. Cities $1,2,\dots,n$ are located at $(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)$, respectively.

Now Xiao Yuan commands several fleets (you may understand this as Xiao Yuan having unlimited military power) stationed at the border fortress, City $1$. His fleets move as follows:

• If a fleet is at coordinate $(x,y)$, then after one day it can move to $(x-1,y+2)$, $(x+1,y+2)$, $(x+2,y+1)$, $(x-2,y+1)$, $(x-1,y-2)$, $(x+1,y-2)$, $(x+2,y-1)$, or $(x-2,y-1)$.

Surrounding the outside is an asteroid belt. When a fleet is at coordinate $(x,y)$ and $x \le 0$ or $y \le 0$ or $m < x$ or $m < y$, the fleet will crash into the asteroid belt, which is something Xiao Yuan does not want.

Now Xiao Yuan wants to attack Cities $2,3,\dots,n$. Each time, he will dispatch a fleet from a city that has already been occupied (City $1$ also counts), send it to City $i$, and attack it. City $i$ will be occupied on the second day after the fleet arrives.

In particular, while Xiao Yuan is sending a fleet to attack or is attacking a city, he will not dispatch another fleet. On the same day a city is occupied, he can immediately dispatch another fleet.

Xiao Yuan wants to know the minimum time needed to occupy all cities.

The attack order does not need to follow $2,3,\dots,n$.

Input Format

The first line contains two integers $n,m$, representing the number of cities and the range of the asteroid belt.

The next $n$ lines each contain two positive integers $(x_i,y_i)$, representing the coordinates of City $i$. It is guaranteed that $1 \le x_i,y_i \le m$.

Output Format

Output one integer $ans$, representing the minimum time required.

2 20
1 1
1 3

3

3 150
1 2
2 4
4 3

4

10 10
1 4
2 3
2 6
3 6
10 3
1 5
4 2
5 3
2 8
9 2

23

查看附件的 example4.in

查看附件的 example4.out

Hint

Explanation for Sample 1.

On day 1, the fleet arrives at position $(3,2)$. On day 2, it reaches the position of City $2$. On day 3, it occupies City $2$. A total of $3$ days are used.

Explanation for Sample 2.

On day 1, the fleet reaches the position of City $2$. On day 2, it occupies City $2$. On day 3, it reaches the position of City $3$. On day 4, it occupies City $3$. A total of $4$ days are used.

Constraints

This problem uses bundled Subtask testdata.

Subtask ID	Test Point ID	$n$	$m$	Special Property	Score
$1$	$1\sim2$	$1\le n\le 7$	$4\le m\le 7$	None	$10$
$2$	$3\sim7$	$1\le n\le 200$	$4\le m\le 70$		$25$
$3$	$8\sim9$	$1\le n\le 150$	$4\le m\le 150$	Yes	$15$
$4$	$10\sim20$	$1\le n\le 2000$		None	$50$

Special property: For every $1 \le i \le n-1$, we have $x_i = x_{i+1}$.

The testdata strictly guarantees that no two different cities share the same coordinates.

Translated by ChatGPT 5