Cat Space Border Conquest

In the tense situation at the interstellar border, a conflict has erupted. The supreme commander of the Meow Empire, Commander Xiao Yuan, has decided to launch a military operation against planet \(Y\).

The whole universe is represented by a Cartesian coordinate system. There are \(n\) cities with coordinates \( (x_1, y_1), (x_2, y_2), \dots, (x_n, y_n) \). Initially, Commander Xiao Yuan stationes an unlimited number of fleets at the frontier fortress located at city 1. The fleets move according to the following rule:

• If a fleet is currently at \( (x,y) \), then in one day it can move to one of the eight positions: \( (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),\ (x-2, y-1) \).

However, surrounding the safe region is an asteroid belt. If a fleet’s coordinate \( (x,y) \) satisfies \( x \le 0 \) or \( y \le 0 \) or \( x > m \) or \( y > m \) (where \( m \) is given), the fleet will crash into the asteroid belt. Therefore, every move must remain within the board \( [1, m] \times [1, m] \).

Commander Xiao Yuan will attack cities \(2, 3, \dots, n\) one by one. Each attack is launched from an already captured city (city 1 is initially captured). When a fleet is dispatched to attack a city \(i\), the fleet travels according to the knight‐move rules above. Once the fleet arrives at the target, the city will be conquered on the next day. Note that while a fleet is en route or an attack on a city is ongoing, no other fleet can be dispatched; however, on the same day a city is conquered, a new fleet can be dispatched immediately.

The attack order can be chosen arbitrarily. Determine the minimum number of days needed to capture all \(n\) cities. Specifically, if the minimum number of knight moves required to go from one captured city to a new city is \(d\), then the attack takes \(d\) days for the move plus one extra day for the actual capture. Hence, if you form a spanning tree where each edge weight represents the minimum knight moves between two cities, the answer is:

\[ \text{Answer} = \text{(sum of knight moves over the spanning tree)} + (n-1). \]

If any city is unreachable from the already conquered cities under the given constraints, output -1.

inputFormat

The first line contains two integers \( n \) and \( m \) (\( 2 \le n \le 100 \), \( m \geq \max\{x_i, y_i\} \) for all \( i \)), representing the number of cities and the board dimension. The following \( n \) lines each contain two integers \( x_i \) and \( y_i \), the coordinates of city \( i \). City 1 is the starting fortress.

outputFormat

Output a single integer: the minimum number of days required to capture all the cities. If it is impossible to capture all cities, output -1.

sample

2 8
1 1
2 3

2