P9709 [KMOI R1] Military Operation

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

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$.**

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 one integer $ans$, representing the minimum time required.

## 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$ | None | $25$ | | $3$ | $8\sim9$ | $1\le n\le 150$ | $4\le m\le 150$ | Yes | $15$ | | $4$ | $10\sim20$ | $1\le n\le 2000$ | $4\le m\le 150$ | 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