All Tracks Algorithms Sorting Bubble Sort Problem

Benny and Segments

Easy-Medium, Sorting, Two-pointer


View Russian Translation

One day Benny was walking and realized that her life was boring. Everything was grey, even roads in the best park were grey.

Therefore she decided to make roads a little bit brighter. She know that every road in the park is a segment laying on the X axis with coordinates Xl, Xr (Xl ≤ Xr). Roads may intersect or overlap.

She chooses any subset of roads and paints them in red. After that she wants to get one continuous red segment. As she really likes number L the length of this segment has to be equal to L.

Your task is to determine if it is possible to choose some subset of roads and paint them to get one red segment with the length equal to L?

If it's possible print in a single line "Yes"(without quotes), otherwise print "No" (without quotes).

Input format

The first line contains one integer T - the number of test cases. Each test case starts with two integers N and L, denoting the number of roads and Benny's favorite number L. The next N lines contain two integers Xl, Xr, denoting the left and right borders of the road.

Output format

For every test case output "Yes" if it is possible to paint some roads and "No" otherwise.


  • 1 ≤ sum of all N ≤ 2 * 103
  • 1 ≤ L ≤ 106
  • 1 ≤ Xl ≤ Xr ≤ 106
  • 1 ≤ N ≤ 20, 1 ≤ Xl ≤ Xr ≤ 200, holds for test cases worth 10% of the problem's score.
  • 1 ≤ N ≤ 100, 1 ≤ Xl ≤ Xr ≤ 200, holds for test cases worth 20% of the problem's score.

Sample Explanation

In the first test case you can choose roads (1; 2) (2; 3) and (3; 4) the result segment is (1; 4) and its length equals 3 (4 - 1 = 3).

In the second case you can not choose any subset that will create segment with the length equal to 4.

5 3
1 2
2 3
3 4
1 5
2 6
2 3
1 2
2 6
Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

March Easy '16

View All Notifications