Space Exploration#2183
The Space Research Department has been assigned the task of photographing objects from space within a designated area. This area is a square with dimensions 50 \times 50 kilometers. If divided into 1 \times 1 kilometer squares, the objects of interest are located at the centers of some of these unit squares.
To facilitate this, a coordinate system is established with the OX axis running from west to east and the OY axis from south to north. Each unit square is assigned coordinates ranging from to , as illustrated in the figure below.
\includegraphics{https://static.e-olymp.com/content/16/16218e9ad52d873f9ca612f4d8a853c8b974c27d.jpg}
A high-resolution camera mounted on a space satellite is used for capturing images. This camera can photograph square areas of the Earth's surface measuring k \times k kilometers. Initially, the camera is aimed at the southwest corner of the specified area, meaning that if a picture is taken, unit squares with coordinates and from to kilometers will be captured.
Using special engines, the satellite's orbit can be adjusted, allowing the shooting area to shift one kilometer to the west, east, or north in a single day. However, moving the shooting area south is not possible. Pictures can be taken between these movements, and the time taken to capture an image is negligible.
The management of the department wants to know: what is the minimum number of days required to photograph all the objects in the specified area?
Your task is to write a program that, given the arrangement of objects and the size of the picture , calculates the minimum time required to photograph all the objects in the specified area.
The first line of the input file contains two integers: and (1 \leq n \leq 1000, 1 \leq k \leq 5).
The next lines each contain two integers: x_i and y_i — the coordinates of the objects in the specified area (1 \leq x_i, y_i \leq 50).
The output file should contain a single integer: the minimum number of days required to photograph all the objects in the specified area.
Example 1
In the first example, the following sequence of actions is possible: take a picture, move times to the east, move north, take a picture, move times to the west, move north, take a picture, move times to the east, move north, take a picture. A total of movements of the shooting area are needed.
In the second example, the objects are located in the same place, but the picture size is larger, allowing the following actions: take a picture, move north, take a picture, move times to the east, take a picture, move north, take a picture. Only movements of the shooting area are needed.
In the third example, there is no need to move the shooting area; just take a picture.
The fourth example corresponds to the figure shown above.