We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Apply
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Search
  4. Distant Pairs

Distant Pairs

Problem
Submissions
Leaderboard
Discussions
Editorial

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 :

image

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:

image

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:

image

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:

image

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

Author

zemen

Difficulty

Expert

Max Score

80

Submitted By

2399

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy