- Prepare
- Algorithms
- Search
- Distant Pairs

# Distant Pairs

# Distant Pairs

We take a line segment of length on a one-dimensional plane and bend it to create a circle with circumference that's indexed from to . For example, if :

We denote a *pair* of points, and , as . We then plot pairs of points (meaning a total of individual points) at various indices along the circle's circumference. We define the distance between points and in pair as .

Next, let's consider two pairs: and . We define distance as the *minimum* of the six distances between any two points among points , , , and . In other words:

For example, consider the following diagram in which the relationship between points in pairs at non-overlapping indices is shown by a connecting line:

Given pairs of points and the value of , find and print the *maximum* value of , where , among all pairs of points.

**Input Format**

The first line contains two space-separated integers describing the respective values of (the number of pairs of points) and (the circumference of the circle).

Each line of the subsequent lines contains two space-separated integers describing the values of and (i.e., the locations of the points in pair ).

**Constraints**

**Output Format**

Print a single integer denoting the maximum , , where .

**Sample Input 0**

```
5 8
0 4
2 6
1 5
3 7
4 4
```

**Sample Output 0**

```
2
```

**Explanation 0**

In the diagram below, the relationship between points in pairs at non-overlapping indices is shown by a connecting line:

As you can see, the maximum distance between any two pairs of points is , so we print as our answer.

**Sample Input 1**

```
2 1000
0 10
10 20
```

**Sample Output 1**

```
0
```

**Explanation 1**

In the diagram below, we have four individual points located at three indices:

Because two of the points overlap, the minimum distance between the two pairs of points is . Thus, we print as our answer.